View Item 

Show simple item record

On the unique satisfiability problem
dc.contributor.authorBlass, Andreasen_US
dc.contributor.authorGurevich, Yurien_US
dc.date.accessioned2006-04-07T17:47:33Z
dc.date.available2006-04-07T17:47:33Z
dc.date.issued1982en_US
dc.identifier.citationBlass, 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.urihttp://www.sciencedirect.com/science/article/B7MFM-4DX44G9-139/2/3e840054184adffaa9bd6a30a035ca31en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/23842
dc.description.abstractUNIQUE 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.extent463303 bytes
dc.format.extent3118 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.language.isoen_US
dc.publisherElsevieren_US
dc.titleOn the unique satisfiability problemen_US
dc.typeArticleen_US
dc.rights.robotsIndexNoFollowen_US
dc.subject.hlbsecondlevelScience (General)en_US
dc.subject.hlbsecondlevelInformation and Library Scienceen_US
dc.subject.hlbsecondlevelComputer Scienceen_US
dc.subject.hlbtoplevelScienceen_US
dc.subject.hlbtoplevelSocial Sciencesen_US
dc.subject.hlbtoplevelEngineeringen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumDepartment of Mathematics, University of Michigan, Ann Arbor, Michigan 48109, USAen_US
dc.contributor.affiliationumDepartment of Computer and Communication Sciences, University of Michigan, Ann Arbor, Michigan 48109, USAen_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/23842/1/0000081.pdfen_US
dc.identifier.doihttp://dx.doi.org/10.1016/S0019-9958(82)90439-9en_US
dc.identifier.sourceInformation and Controlen_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
0000081.pdf
Size:
452.4KB
Format:
PDF
View/Open

Show simple item record

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.