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.
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
np hardness;np complete;promise problems
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).