¿

¿ implica ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

cc.complexity-theory conditional-results nexp structural-complexity argentpepper
fuente

Sí, E = NE implica EXP = NEXP que se puede probar usando el argumento de relleno.

Mohammad Al-Turkistany

No es obvio para mí por qué EXP = NEXP implica E = NE. Si eso fuera cierto, entonces cualquier algoritmo

time para Succinct3SAT se puede convertir en un algoritmo

-time para Succinct3SAT. ¿Quizás invirtió las cosas y quiso preguntar sobre la otra implicación?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Ryan Williams

¡Y luego P = NP si P = 0 o N = 1!

Daniel Apon

Si. Supongo que es un problema de tarea.

Mohammad Al-Turkistany

No entiendo el cierre de esta pregunta como "no es una pregunta real" después de haber sido editada como una pregunta razonable (aunque el texto de la pregunta no es interesante). Por ejemplo, el comentario de Ryan Williams puede ser una respuesta.

Tsuyoshi Ito

Respuestas:

Esto está abierto, que yo sepa. Podría ser demostrable (porque su hipótesis puede ser falsa) o puede ser difícil demostrar que cualquier algoritmo de time para Succinct3SAT puede convertirse en un algoritmo de -time para Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

En general, los teoremas de este tipo se denominan "colapsos descendentes" que dicen que si dos clases "grandes" son iguales, entonces dos clases "más pequeñas" son iguales. Estos teoremas son raros. Por lo general, puede probar un "colapso hacia arriba" (clases pequeñas iguales implica clases más grandes iguales, como implica ) o su contraposición, una "separación hacia abajo". $P = NP$ $NEXP = EXP$

Algo similar a lo que quieres es el teorema de Hartmanis, Immerman y Sewelson ( http://dl.acm.org/citation.cfm?id=808769 ) que $NE = E$ $\iff$ cada conjunto escasa en está contenido en . Esto da un "colapso hacia abajo", pero sólo para los conjuntos de Disperso (aquellos conjuntos que contienen sólo cadenas de longitud ). $NP$ $P$ $poly(n)$ $n$

Ryan Williams
fuente