On the unique satisfiability problem
dc.contributor.author | Blass, Andreas | en_US |
dc.contributor.author | Gurevich, Yuri | en_US |
dc.date.accessioned | 2006-04-07T17:47:33Z | |
dc.date.available | 2006-04-07T17:47:33Z | |
dc.date.issued | 1982 | en_US |
dc.identifier.citation | Blass, Andreas, Gurevich, Yuri (1982)."On the unique satisfiability problem." Information and Control 55(1-3): 80-88. <http://hdl.handle.net/2027.42/23842> | en_US |
dc.identifier.uri | http://www.sciencedirect.com/science/article/B7MFM-4DX44G9-139/2/3e840054184adffaa9bd6a30a035ca31 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/23842 | |
dc.description.abstract | UNIQUE SAT is the problem of deciding whether a given Boolean formula has exactly one satisfying truth assignment. This problem is a typical (moreover complete) representative of a natural class of problems about unique solutions. All these problems belong to the class DIFP = L1 L2:L1, L2 [epsilon] NP studied by Papadimitriou and Yannakakis. We consider the relationship between these two classes, particularly whether UNIQUE SAT is DIFP-complete: It is if NP = co NP. We construct an oracle relative to which UNIQUE SAT is not complete for DIFP, and another oracle relative to which UNIQUE SAT is complete for DIFP, whereas NP [not equal to] co NP. | en_US |
dc.format.extent | 463303 bytes | |
dc.format.extent | 3118 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | en_US |
dc.title | On the unique satisfiability problem | en_US |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | en_US |
dc.subject.hlbsecondlevel | Science (General) | en_US |
dc.subject.hlbsecondlevel | Information and Library Science | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.subject.hlbtoplevel | Social Sciences | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109, USA | en_US |
dc.contributor.affiliationum | Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, Michigan 48109, USA | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/23842/1/0000081.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1016/S0019-9958(82)90439-9 | en_US |
dc.identifier.source | Information and Control | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.