DocumentCode
2891799
Title
On selecting a satisfying truth assignment
Author
Papadimitriou, Christos H.
Author_Institution
Dept. of Comput. Sci. & Eng., California Univ., San Diego, CA, USA
fYear
1991
fDate
1-4 Oct 1991
Firstpage
163
Lastpage
169
Abstract
The complexity of certain natural generalizations of satisfiability, in which one of the possibly exponentially many satisfying truth assignments must be selected, is studied. Two natural selection criteria, default preference and minimality (circumscription), are considered. The thrust of the complexity results seems to be that hard problems become harder, while easy problems remain easy. This consideration yields as a byproduct a new and very natural polynomial-time randomized algorithm for 2SAT
Keywords
computational complexity; 2SAT; circumscription; complexity; default preference; minimality; natural generalizations; polynomial-time randomized algorithm; satisfiability; satisfying truth assignment selection; selection criteria; Computer science; Hypercubes; Polynomials; Tail;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location
San Juan
Print_ISBN
0-8186-2445-0
Type
conf
DOI
10.1109/SFCS.1991.185365
Filename
185365
Link To Document