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.

  • 12
    $\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
  • 4
    $\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

