¿Qué evidencia tenemos para

Siguiendo la sugerencia de Josh Grochow, estoy convirtiendo mi comentario de una pregunta anterior en una nueva pregunta.

¿Qué evidencia tenemos para ?$\mathsf{UP} \neq \mathsf{NP}$

Aquí, $\mathsf{UP}$ es la clase de lenguajes reconocibles por las máquinas de Turing no deterministas de tiempo polinómico que tienen una ruta de aceptación única en instancias de "sí" y ninguna ruta de aceptación en instancias de "no".

$\mathsf{UP} \subseteq \mathsf{NP}$$\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$$\mathsf{UP}$

Incluso, Selman y Yacobi conjeturaron que no existe un par disjunto tal que todos los separadores de sean -puros para . Esta conjetura implica que .( A , B ) ( A , B ) ≤ p T N P U P ≠ N $NP$$(A, B)$$(A, B)$$\le_T^p$$NP$$UP \ne NP$

S. Even, A. Selman y J. Yacobi. La complejidad de los problemas prometedores con las aplicaciones de criptografía de clave pública. Información y control, 61: 159-173, 1984.