Conséquences de UP est égal à NP

EDIT au 2011/02/08: Après avoir trouvé et lu des références, j'ai décidé de séparer la question d'origine en deux questions distinctes. Voici la partie concernant UP vs NP, pour la partie classes syntaxiques et sémantiques, veuillez consulter Avantages pour les classes syntaxiques et sémantiques .

N $\mathsf{UP}$ (le temps polynomial sans ambiguïté, voir wiki et le zoo pour les références) est défini comme des langues décidées par des avec une contrainte supplémentaire qui$\mathsf{NP}$

• Il existe au plus un chemin de calcul acceptant sur n'importe quelle entrée.

Les relations précises entre vs et vs sont toujours ouvertes. Nous savons que des fonctions unidirectionnelles dans le pire des cas existent si et seulement si , et il y a des oracles relatifs à toutes les possibilités des inclusions .U P U P N P P ≠ U P P ⊆ U P ⊆ N $\mathsf{P}$$\mathsf{UP}$$\mathsf{UP}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{UP}$$\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$

Je suis intéressé par la raison pour laquelle vs est une question importante. Les gens ont tendance à croire (au moins dans la littérature ) que ces deux classes sont différentes, et mon problème est:N $\mathsf{UP}$$\mathsf{NP}$

Si , y a-t-il de "mauvaises" conséquences?$\mathsf{UP} = \mathsf{NP}$

Il y a un article sur le blog de la complexité en 2003. Et si ma compréhension est correcte, le résultat de Hemaspaandra, Naik, Ogiwara et Selman montre que si

• Il existe un langage tel que pour chaque formule satisfaisable, il existe une affectation satisfaisante unique avec dans , L $\mathsf{NP}$$L$$\phi$( ϕ , x ) $x$$(\phi,x)$$L$

puis la hiérarchie polynomiale s'effondre au deuxième niveau. Aucune implication de ce type n'est connue si tient.$\mathsf{UP} = \mathsf{NP}$

On sait que implique puisque Kobler, Schoning et Toran ont prouvé que si et seulement si . Il est facile de voir que est contenu dans .S p a n P = # P U P = N P S p a n P = # P # P S p a n $\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf {\#P}$$\mathsf {SpanP}$

Une fonction est dans s'il y a un transducteur de machine de Turing tel que pour tout , est le nombre de sorties distinctes de sur entrée .S p a n P N P M x f ( x ) M $f : Σ^* →\mathbb N$$\mathsf{SpanP}$$\mathsf {NP}$$M$$x$$f(x)$$M$$x$

J. Kobler, U. Schoning et J. Toran. Sur le comptage et l'approximation , Acta Informatica, 26: 363-379, 1989.