Problèmes NP-Complete qui admettent un algorithme efficace sous la promesse d'une solution unique

14

Je lisais récemment un très bon article de Valiant et Vazirani qui montre que si NP≠RP , il ne peut pas y avoir d'algorithme efficace pour résoudre SAT même sous la promesse qu'il est insatisfaisant ou qu'il a une solution unique. Montrant ainsi que SAT n'admet pas d'algorithme efficace même sous la promesse qu'il y aura au plus une solution.

Grâce à une réduction parcimonieuse (une réduction qui préserve le nombre de solutions), il est facile de voir que la plupart des problèmes NP-complets (je pourrais y penser) n'admettent pas non plus un algorithme efficace même sous la promesse qu'il y ait au plus une solution (sauf si ). Les exemples seraient VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.NP=RP

Par conséquent, je me demandais s'il y avait un problème NP-complet qui était connu pour admettre un algorithme poly-temps sous une promesse d'unicité.

np-hardness np-complete unique-solution promise-problems Diable
la source
12
Ce n'est pas une très bonne réponse, mais il existe de nombreux problèmes NP-complete dont les instances ont toujours zéro ou plusieurs solutions. Considérons le graphique 3-coloration par exemple; les solutions viennent par groupes de 6 puisque vous pouvez toujours permuter les couleurs. Un tel problème a un algorithme de temps polynomial sous la promesse d'au plus une solution. En particulier, s'il y a au plus une coloration 3, il ne peut pas y en avoir, et donc l'algorithme peut simplement rejeter.
Mikhail Rudoy
4
Le problème du cycle hamiltonien admet un algorithme de temps plus rapide (mais toujours exponentiel) sous la promesse d'unicité. Il ne répond pas directement à votre question, car ce n'est pas polynomial, mais au moins c'est un problème de comportement différent alors SAT
ivmihajlin
4
Comme dans le commentaire de Mikhail Rudoy, ​​tester l'existence d'un cycle hamiltonien dans les graphes à 3 régularités est trivial avec une hypothèse d'unicité. Chaque front participe à un nombre pair de cycles hamiltoniens, il ne peut donc jamais y en avoir exactement un.
David Eppstein

Réponses:

10

Aucun problème NP-complet n'est connu pour admettre un algorithme à temps polynomial sous promesse d'unicité. Le théorème de Valiant et Vazirani s'applique à tout problème naturel connu de NP-complet.

Pour tous les problèmes connus de NP-complet, il y a une réduction parcimonieuse de 3SAT. Oded Goldreich déclare que "toutes les réductions connues parmi les NP- les problèmes complets sont parcimonieux ou peuvent être facilement modifiés pour l'être. "( Complexité informatique: une perspective conceptuelle par Oded Goldreich ).

Mohammad Al-Turkistany
la source
2
Voir aussi le théorème 2.1: wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf
Mohammad Al-Turkistany