I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution. Thus showing that SAT does not admit an efficient algorithm even under the promise of there being at most one solution.

Through a parsimonious reduction (a reduction that preserves the number of solutions), it is easy to see that most NP-complete problems (I could think of) also do not admit an efficient algorithm even under the promise of there being at most one solution (unless $\mathbf{NP = RP}$). Examples would be VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.

Hence I was wondering if there was any NP-complete problem that was known to admit a poly-time algorithm under a uniqueness promise.

  • 13
    $\begingroup$ This isn't a very good answer, but there are many NP-complete problems whose instances always have either zero or more than one solution. Consider graph 3-coloring for example; the solutions come in groups of 6 since you can always permute the colors. Any such problem has a polynomial time algorithm under the promise of at most one solution. In particular, if there is at most one 3-coloring then there cannot be any, and so the algorithm can just reject. $\endgroup$ – Mikhail Rudoy Feb 14 '17 at 9:24
  • 4
    $\begingroup$ Hamiltonian cycle problem admits faster (but still exponential) time algorithm under the uniqness promiss. It is not directly answering your question, because it's not polynomial, but at least this is a problem with differen tbehaviour then SAT $\endgroup$ – ivmihajlin Feb 14 '17 at 9:53
  • 5
    $\begingroup$ As in Mikhail Rudoy's comment, testing for the existence of a Hamiltonian cycle in 3-regular graphs is trivial with a uniqueness assumption. Each edge participates in an even number of Hamiltonian cycles, so there can never be exactly one. $\endgroup$ – David Eppstein Feb 15 '17 at 5:55

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem.

For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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