HiveBrain v1.2.0
Get Started
← Back to all entries
principleModerate

If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satuniqueimplyoneshowsthatdoes

Problem

Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, if someone shows that UNIQUE k-SAT is in P, does it imply P=NP?

References

-
L. G. Valiant and V. V. Vazirani, "NP is as easy as detecting unique solutions." Theoretical Computer Science 47:85–93, 1986. (PDF on ScienceDirect.)

-
C. Calabro, R. Impagliazzo, V. Kabanets and R. Paturi, "The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs". Journal of Computer and System Sciences 74(3):386–393, 2008. (PDF at ACM Digital Library; free PDF.)

Solution

This is still an open question; UP is not known to be equivalent to NP. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under which P contains UP but P is still not equivalent to NP.

Context

StackExchange Computer Science Q#33225, answer score: 12

Revisions (0)

No revisions yet.