Quelles preuves avons-nous pour

Suite à la suggestion de Josh Grochow, je convertis mon commentaire d'une question précédente en une nouvelle question.

Quelles preuves avons-nous pour ?$\mathsf{UP} \neq \mathsf{NP}$

Ici est la classe de langages reconnaissable par les machines de Turing non déterministes à temps polynomial qui ont un chemin d'acceptation unique sur les instances "oui" et aucun chemin d'acceptation sur les instances "non".$\mathsf{UP}$

Évidemment , mais pourquoi penserions-nous que le confinement est strict? La preuve que je peux trouver est la séparation d'oracle : sous réserve d'un oracle aléatoire, . De plus, le Complexity Zoo suggère que \ mathsf {UP} ne semble pas avoir de problèmes complets.$\mathsf{UP} \subseteq \mathsf{NP}$$\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$$\mathsf{UP}$

Même, Selman et Yacobi ont supposé qu'il n'existe pas de paire disjointe sorte que tous les séparateurs de soient -hard pour . Cette conjecture implique que .$NP$$(A, B)$$(A, B)$$\le_T^p$$NP$$UP \ne NP$

S. Even, A. Selman et J. Yacobi. La complexité des problèmes de promesse avec les applications à la cryptographie à clé publique. Information et contrôle, 61: 159-173, 1984.