¿Qué evidencia tenemos para

17

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

¿Qué evidencia tenemos para ?UPNP

Aquí, UPAG 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".

UPAGnortePAGPAGUPAGnortePAGUPAG

Sasho Nikolov
fuente
66
Discusión relacionada aquí: cstheory.stackexchange.com/q/3887/1800
Hsien-Chih Chang 張顯 之
@ Hsien-ChihChang 張顯 之 hm, tal vez mi pregunta es duplicada. Si crees que sí, puedo marcarlo para eliminarlo.
Sasho Nikolov
44
No creo que esto sea un duplicado. Creo que las respuestas a la otra pregunta contarían como respuestas a esta, pero no necesariamente al revés: podría haber razones para creer que nortePAGUPAG no tienen la forma " Si nortePAG=UPAG , entonces ocurre alguna (otra) consecuencia de mala complejidad ".
Joshua Grochow
2
La mejor evidencia es que tenemos límites superiores sub-exponenciales en algunos problemas naturales intratables en UP (como las versiones de decisión del logaritmo discreto y la factorización de enteros), mientras que no podemos encontrar dicho límite superior para ciertos problemas NP-completos como 3SAT. Tal límite superior para 3SAT es imposible asumiendo la hipótesis del tiempo exponencial.
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany: Pero esos problemas están en , por lo que si , aún estarían en , por lo que no sería -completo a menos que ...N P = U P N Pc o N P N P N P = c o N PUPAGCoUPAGnortePAG=UPAGnortePAGConortePAGnortePAGnortePAG=ConortePAG
Joshua Grochow

Respuestas:

5

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 PNP(A,B)(A,B)TpNPUPNPAG

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.

Mohammad Al-Turkistany
fuente
1
Esto también funciona como una buena respuesta para la publicación relacionada cstheory.stackexchange.com/questions/3887/…
Mohammad Al-Turkistany
1
Esta fuerte conjetura también implica que . nortePAGConortePAG
Mohammad Al-Turkistany