0
$\begingroup$

Valiant & Vazirani proved SAT transforms 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 s 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.)

$\endgroup$
6
  • $\begingroup$ There is standard reduction SAT to k-SAT and even to 3-SAT. $\endgroup$
    – joro
    Dec 3, 2014 at 13:06
  • 3
    $\begingroup$ The reductions in the Calabro et el. paper are again randomized. So no, it doesn’t imply P = NP. See also people.cs.uchicago.edu/~fortnow/papers/sep.ps . $\endgroup$ Dec 3, 2014 at 15:00
  • 1
    $\begingroup$ cstheory.stackexchange.com is likely a more appropriate forum. $\endgroup$ Dec 3, 2014 at 16:10
  • $\begingroup$ Therefore it should lead to "NP=RP", shouldn't it? Yes, but computer scientists are too busy to reply. $\endgroup$
    – Husrev
    Dec 4, 2014 at 14:05
  • $\begingroup$ Yes, NP = RP sounds right. The Valiant-Vazirani reduction isn't a proper reduction as it has only a small probability of success, nevertheless using the self-reducibility of SAT, this should still give a randomized algorithm for finding satisfying assignments, and therefore NP = RP. $\endgroup$ Dec 5, 2014 at 11:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.