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

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

• 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. Sep 13, 2017 at 20:57

1 Answer

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.

• 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. Jun 19 at 18:58