Intuition pour la classe UP

La classe UP est définie comme telle:

La classe de problèmes de décision pouvant être résolus par une machine NP telle que

Si la réponse est «oui», exactement un chemin de calcul est accepté.

Si la réponse est «non», tous les chemins de calcul sont rejetés.

J'essaie de développer l'intuition pour cette définition.

Peut-on dire que les problèmes UP sont les problèmes avec des solutions uniques (par exemple la factorisation principale)?

Cela me semble proche de la vérité; mais je ne peux pas m'empêcher de penser que cela signifierait, puisque UP contient P et est contenu dans NP, que dans le cas où P = NPnous aurions cela P = UP = NP, donc tous les problèmes NPont des solutions uniques, ce qui semble être quelque chose qui n'est pas prouvé: P != NPpar reductio ad absurdum. J'espère qu'il n'y a pas trop de conjectures et d'ondulations à la main dans ce paragraphe à votre goût.

Votre confusion semble être due au fait que les problèmes ont plus d'une façon de définir une «solution» (ou témoin). Le type de solution ne fait pas partie de la définition du problème. Par exemple, pour la coloration des graphes, le type de solution évident est une affectation d'une couleur pour chaque sommet (en utilisant au plus le nombre de couleurs requis); cependant, par le théorème de Gallai – Hasse – Roy – Vitaver$\mathsf{NP}$un autre type de solution qui fonctionne aussi bien est l'affectation d'une orientation à chaque arête (créant des trajectoires dirigées d'au plus le nombre de sommets requis). Ces deux types de solutions peuvent tous deux être vérifiés en temps polynomial, mais par différents algorithmes, et ils ont également des propriétés combinatoires différentes. Par exemple, pour une instance de problème typique, le nombre d'attributions de couleur de sommet sera différent du nombre d'orientations de bord. De nombreuses recherches sur l'accélération des algorithmes exponentiels pour les problèmes de type NP peuvent être interprétées comme la recherche d'une nouvelle famille de solutions au même problème qui a moins de possibilités de vérification.

Chaque problème dans a une «solution» N P constituée uniquement de la chaîne vide. Pour vérifier qu'il s'agit d'une solution, vérifiez simplement que la chaîne de solution est vide, puis exécutez l'algorithme de temps polynomial pour l'instance de problème. Avec ce type de solution, tous les cas de oui a exactement une solution valable et chaque instance ne dispose nulle, répondant à la définition de U P et montrant que P ⊂ U P . Si P = N P, alors la même solution de chaîne vide fonctionnerait également pour chaque problème dans N P , montrant que N P = U $\mathsf{P}$$\mathsf{NP}$$\mathsf{UP}$$\mathsf{P}\subset\mathsf{UP}$$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}=\mathsf{UP}$. Il n'y a donc pas de contradiction entre le fait que la solution de chaîne vide est unique et le fait qu'un autre type de solution pour le même problème n'est pas unique.

Je suis d'accord avec le commentaire de Shaull selon lequel l'intuition d'avoir un témoin unique est correcte, mais subtile. L'argument dans votre dernier paragraphe peut être techniquement précis, et met en évidence la subtilité de par rapport à N P . En particulier, le problème dans votre dernier paragraphe est essentiellement la question de savoir si N P M V ⊆ c N P S V :$\mathsf{UP}$$\mathsf{NP}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

est la classe des fonctions à valeurs multiples partielles calculables en temps polynomial non déterministe, c'est-à-dire que chaque branche non déterministe acceptante obtient une valeur de sortie (s'il n'y a pas de chemin d'acceptation sur une entrée, alors il n'y a pas de sortie, conduisant au fait que cesfonctionsne doivent être quepartielles). Ceci est étroitement lié à la version de recherche desproblèmes N $\mathsf{NPMV}$$\mathsf{NP}$

est la classe desfonctions à évaluationuniquedans N P M V , c'est-à-dire que plusieurs branches peuvent accepter, mais si des branches acceptent, toutes les branches acceptantes doivent sortir la même valeur.$\mathsf{NPSV}$$\mathsf{NPMV}$

Intuitivement, votre dernier paragraphe parle de savoir si vous pouvez toujours sélectionner, parmi les témoins pour un vérificateur donné d'un problème , un seul témoin. Il s'agit de savoir si chaque fonction N P M V a un raffinement N P S V (noté N P M V ⊆ c N P S V ). Si tel est le cas, la hiérarchie polynomiale s'effondre (voir Hemaspaandra, Naik, Ogihara et Selman "Computing Solutions Uniquely Collapss the Polynomial Hierarchy" ).$\mathsf{NP}$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{UP}$$\mathsf{NP} = \mathsf{UP}$$L \in \mathsf{NP}$$\mathsf{UP}$$L$$\mathsf{NP}$$L$