Problemas NP-Complete que admiten un algoritmo eficiente bajo la promesa de una solución única

Recientemente estuve leyendo un artículo muy bueno de Valiant y Vazirani que muestra que si , entonces no puede haber un algoritmo eficiente para resolver SAT incluso bajo la promesa de que es insatisfactorio o tiene una solución única. De este modo, se demuestra que SAT no admite un algoritmo eficiente, incluso bajo la promesa de que existe como máximo una solución.$\mathbf{NP \neq RP}$

A través de una reducción parsimoniosa (una reducción que preserva el número de soluciones), es fácil ver que la mayoría de los problemas con NP completo (se me ocurre) tampoco admiten un algoritmo eficiente, incluso bajo la promesa de que existe como máximo una solución (a menos que ). Los ejemplos serían VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.$\mathbf{NP = RP}$

Por lo tanto, me preguntaba si había algún problema de NP completo que admitiera un algoritmo de poli-tiempo bajo una promesa de unicidad.

No se sabe que ningún problema NP-completo admita un algoritmo de tiempo polinómico bajo promesa de unicidad. El teorema de Valiant y Vazirani se aplica a cualquier problema natural de NP completo conocido.

Para todos los problemas conocidos de NP completo, hay una reducción parsimoniosa de 3SAT. Oded Goldreich afirma el hecho de que "todas las reducciones conocidas entre naturales $NP$los problemas completos son parsimoniosos o pueden modificarse fácilmente para serlo ". ( Complejidad computacional: una perspectiva conceptual de Oded Goldreich ).