Faz

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

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

Sim, E = NE implica EXP = NEXP, o que pode ser comprovado usando o argumento padding.

Mohammad Al-Turkistany

Não é óbvio para mim por que EXP = NEXP implica E = NE. Se isso fosse verdade, qualquer algoritmo de horas para Succinct3SAT pode ser convertido em um algoritmo de horas para Succinct3SAT. Talvez você tenha revertido as coisas e quis perguntar sobre a outra implicação?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Ryan Williams

E então P = NP se P = 0 ou N = 1!

22612 Daniel Apon

Sim. Eu acho que é um problema de lição de casa.

Mohammad Al-Turkistany

Não entendo o fechamento desta questão como "não é uma pergunta real" depois que ela foi editada para uma pergunta razoável (embora o texto da pergunta não seja interessante). Por exemplo, o comentário de Ryan Williams pode ser uma resposta para ele.

Tsuyoshi Ito

Respostas:

Isso está aberto, até onde eu sei. Pode ser possível (porque sua hipótese pode ser falsa) ou apenas ser difícil mostrar que qualquer algoritmo de horas para Succinct3SAT pode ser convertido em um algoritmo de horas para Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

Em geral, teoremas desse tipo são chamados de "colapsos descendentes", que dizem que se duas classes "grandes" são iguais, então duas classes "menores" são iguais. Esses teoremas são raros. Normalmente, você pode provar um "colapso ascendente" (classes pequenas iguais implica classes maiores iguais, como implica ) ou seu contrapositivo, uma "separação descendente". $P = NP$ $NEXP = EXP$

Algo na linha do que você quer é o teorema de Hartmanis, Immerman e Sewelson ( http://dl.acm.org/citation.cfm?id=808769 ) que cada conjunto disperso em estiver contido em . Isso fornece um "colapso para baixo", mas apenas para os conjuntos esparsos (aqueles que contêm apenas cadeias de de comprimento ). $NE = E$ $\iff$ $NP$ $P$ $poly(n)$ $n$

Ryan Williams
fonte