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.)

Improve this question
$\endgroup$
6
  • $\begingroup$ There is standard reduction SAT to k-SAT and even to 3-SAT. $\endgroup$
    – joro
    Commented 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$
    – Emil Jeřábek
    Commented Dec 3, 2014 at 15:00
  • 1
    $\begingroup$ cstheory.stackexchange.com is likely a more appropriate forum. $\endgroup$
    – Ryan Budney
    Commented 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
    Commented 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$
    – Emil Jeřábek
    Commented Dec 5, 2014 at 11:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .