Consequências do não-determinismo acelerando a computação determinística

Se $\mathsf{NP}$ contiver uma classe de problemas de tempo superpolinomial, ou seja,

para alguma função $t \in n^{\omega(1)}$ , $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$ ,

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

Mas existem outras conseqüências interessantes não triviais (isto é, não são uma conseqüência de ) se o não determinismo puder acelerar os cálculos determinísticos?$\mathsf{P} \subsetneq \mathsf{NP}$

Eu encontrei uma conseqüência relacionada.

Digamos que contenha , onde . Acontece que este é apenas o tempo necessário para diagonalizar contra . Especificamente, crie a seguinte máquina:$NEXP$$DTIME(2^{O(t)})$$t = n^{\omega(1)}$$P/poly$

Na entrada de comprimento , considerar o Turing máquina . Para cada sequência de conselhos possível de comprimento e toda sequência de bits possível de comprimento , execute em com a orientação e rejeite após etapas se você ainda não aceitou. Registre seus resultados em uma tabela. Este procedimento é executado em .$x$$n$$n^{th}$$M$$t$ $b$$n$$M$$b$$a$$t$$DTIME(2^{O(t)})$

Na entrada , se pelo menos metade das strings de orientação fizer com que seja rejeitada, em vez disso, definiremos que é correto que nosso algoritmo aceite (caso contrário, é correto que nosso algoritmo rejeite). Quaisquer cadeias de aconselhamento que causaram para obter errado (ou seja, pelo menos metade das cordas conselho) agora são jogados para fora da mesa. Em seguida, repetimos o processo na entrada : se pelo menos metade das strings de conselhos sobreviventes fizerem com que seja rejeitada, nosso algoritmo aceitará (e rejeitará o contrário). Continue assim para todas as entradas de comprimento (embora realmente, apenas$0^n$$M$$M$$0^n$$0^{n-1}1$$M$$n$$t$ deles são necessários - depois de muitas contribuições, jogamos fora todas as orientações possíveis).

Claramente, esse idioma pode ser decidido em , que assumimos estar no . Por outro lado, ele não pode estar em : o conjunto de entradas de comprimento diagonaliza contra a perspectiva de ser usado para decidir o idioma.$DTIME(2^{O(t)})$$NEXP$$P/Poly$$n$$M_n$

Portanto, obtemos , o que seria interessante.$NEXP \not \subset P/poly$

Vou deixar a pergunta em aberto, caso alguém venha com outra coisa.