Exemples dans lesquels l'unicité de la solution facilite la recherche

La classe de complexité comprend les problèmes de qui peuvent être résolus par une machine de Turing polynomiale non déterministe qui en a au plus un qui accepte le chemin de calcul. C'est-à-dire que la solution, s'il y en a une, est unique en ce sens. Il est hautement improbable que tous les problèmes de se trouvent dans , car, selon le théorème de Valiant-Vazirani, cela impliquerait l'effondrement de .$\mathsf{UP}$$\mathsf{NP}$$\mathsf{UP}$$\mathsf{P}$$\mathsf{NP}=\mathsf{RP}$

D'autre part, aucun -problem n'est connu pour être -complet, ce qui suggère que l'exigence de solution unique les rend encore plus faciles.$\mathsf{UP}$$\mathsf{NP}$

Je cherche des exemples où l'hypothèse d'unicité conduit à un algorithme plus rapide.

Par exemple, en examinant les problèmes de graphes, une clique maximale dans un graphique peut-elle être trouvée plus rapidement (bien que toujours en temps exponentiel), si nous savons que le graphique a une clique maximale unique ? Qu'en est-il de la colorabilité unique , du chemin hamiltonien unique, de l'ensemble dominant minimal unique, etc.?$k$

En général, nous pouvons définir une version à solution unique de tout problème complet de , en les redimensionnant à . Est-il connu pour l'un d'entre eux que l'ajout de l'hypothèse d'unicité conduit à un algorithme plus rapide? (Permettant qu'il reste toujours exponentiel.)$\mathsf{NP}$$\mathsf{UP}$

3-SAT peut être un tel problème. Actuellement, la meilleure limite supérieure pour Unique 3-SAT est exponentiellement plus rapide que pour le 3-SAT général. (L'accélération est exponentielle bien que la réduction de l'exposant soit minime.) Le détenteur du record pour le cas unique est ce document de Timon Hertli.

L'algorithme de Hertli repose sur l'important algorithme PPSZ de Paturi, Pudlák, Saks et Zane pour $k$ -SAT, qui, je crois, est toujours le plus rapide pour (voir aussi cet article de l'encyclopédie). L'analyse initiale montrait de meilleures limites pour Unique k -SAT que pour le général k -SAT lorsque k = 3 , 4 ; par la suite, cependant, Hertli a montré dans un article différent$k \geq 5$$k$$k$$k = 3, 4$que vous puissiez obtenir les mêmes limites pour l’algorithme PPSZ (légèrement modifié), sans présumer de l’unicité. Donc, peut-être que l'unicité peut aider, et cela peut certainement simplifier l'analyse de certains algorithmes, mais notre compréhension du rôle de l'unicité pour SAT continue de croître.$k$

Il est prouvé que Unique -SAT n’est pas beaucoup plus facile que le général k -SAT. Le temps fort Exponentielle Hypothesis (SETH) affirme qu'il n'y a pas δ < 1 tel que n -variable k -SAT est résoluble en O *$k$$k$$\delta < 1$$n$$k$ pour chaque constante k ≥ 3 . Il a été montré dans unarticlede Calabro, Impagliazzo, Kabanets et Paturi que, si SETH se vérifiait, la même affirmation serait vraie pour Unique k -SAT. Aussi, si k général$O^*(2^{\delta n})$$k \geq 3$$k$$k$-SAT nécessite un temps exponentielle, soit il y a un tel que le général k -SAT ne peut pas être résolu en temps O * ( 2 ε n ) , le même doit être vrai pour unique 3-SAT. Voir le papier pour l'énoncé le plus général. $k \geq 3, \epsilon > 0$$k$$O^*(2^{\epsilon n})$

(Note: l' notation supprime les facteurs polynôme dans la longueur d'entrée.)$O^*$

Le plus court problème de chemin d'accès disjoint à 2 sommets dans les graphes non dirigés sommets récemment résolus (ICALP14) par A. Bjorklund et T. Husfeldt. Mais la solution déterministe est pour le cas de l'existence d'une solution unique. Dans le cas où il y aurait plus d'une solution, ils ont montré que le problème appartenait à RP . Comme les auteurs de l'article l'ont mentionné, on ne sait pas si le problème est dans P dans le scénario général.

En dehors de la théorie de la complexité et de l'analyse des algorithmes, l'hypothèse selon laquelle il ne peut y avoir qu'une seule solution constitue la base de certaines des règles standard utilisées pour déduire la solution dans les énigmes de Sudoku. Ces règles impliquent généralement de rechercher des moyens permettant à certaines parties du puzzle d’avoir deux solutions ou plus qui n’interagissent pas avec le reste du puzzle. Cela ne peut pas arriver dans la solution réelle, donc si un modèle qui menace de le trouver est trouvé, il doit alors être cassé, permettant au résolveur de déduire des contraintes sur ce à quoi la solution réelle peut ressembler. Voir http://www.brainbashers.com/sudokuuniquerectangles.asp pour quelques exemples de règles de déduction basées sur l'unicité.

En mentionnant un autre résultat de Björklund, si vous avez la garantie qu'il y a au plus un cycle hamiltonien dans un graphique, vous pouvez décider si un graphique est hamiltonien plus rapidement que vous ne le pouvez en général.$G$

L'hypothèse d'uniqeness signifie que la parité du nombre de Ham. chemins est le même que décider si le graphique est hamiltonien.

$O(1.619^n)$$O^*(1.657^n)$$O(n^22^n)$