11
$\begingroup$

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

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

  2. 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$
1
  • $\begingroup$ Valiant & Vazirani showed that SAT is reducible to UNAMBIGUOUS SAT under RP reductions. In second case you are speaking about UNIQUE SAT which is $\mathsf{NP}$-hard. $\endgroup$
    – rus9384
    Commented Sep 13, 2017 at 20:57

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ just a minor note: Charles Rackoff in 1982 on Relativized Questions Involving Probabilistic Algorithms (dl.acm.org/doi/pdf/10.1145/322290.322306), he showed that UP = P and P != NP under some oracle. The paper you mentioned is stronger than the later since Rackoff's paper conditioned that UP has exactly one accepting path for all inputs. $\endgroup$
    – user777
    Commented Jun 19, 2022 at 18:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.