Existem separações naturais na hierarquia de tempo não determinística?

O teorema original da hierarquia de tempo não determinística é devido a Cook (o link é para S. Cook, uma hierarquia para complexidade de tempo não determinística , JCSS 7 343–353, 1973). O teorema afirma que, para qualquer número real e , se então NTIME ( ) está estritamente contido em NTIME ( ).r 2 1 ≤ r 1 < r 2 n r 1 n r $r_1$$r_2$$1 \le r_1 \lt r_2$$n^{r_1}$$n^{r_2}$

Uma parte essencial da prova usa a diagonalização (não especificada) para construir uma linguagem de separação dos elementos da classe menor. Não apenas esse é um argumento não construtivo, mas as linguagens obtidas pela diagonalização geralmente não fornecem outro insight além da própria separação.

Se queremos entender a estrutura da hierarquia NTIME, provavelmente a seguinte pergunta precisa ser respondida:

Existe um idioma natural em NTIME ( ), mas não em NTIME ( )? n $n^{k+1}$$n^k$

Um candidato pode ser k-ISOLATED SAT , que exige encontrar uma solução para uma fórmula CNF sem outras soluções dentro da distância de Hamming k. No entanto, provando o limite inferior parece é complicado, como de costume. É óbvio que a verificação de uma bola k de Hamming está livre de possíveis soluções "deveria" exigir que tarefas diferentes sejam verificadas, mas isso não é fácil de provar . (Nota: Ryan Williams aponta que esse limite inferior para k- ISOLATED SAT provaria realmente P ≠ NP, portanto esse problema não parece ser o candidato certo.)$\Omega(n^k)$$k$

Observe que o teorema é válido incondicionalmente, independentemente de separações não comprovadas, como P vs. NP. Uma resposta afirmativa a esta pergunta não resolveria P vs. NP, a menos que possua propriedades adicionais como $k$ ISOLADO SAT acima. Uma separação natural de NTIME talvez ajude a iluminar parte do comportamento "difícil" de NP, a parte que deriva sua dificuldade de uma sequência crescente e infinita de dureza.

Como os limites inferiores são difíceis, aceitarei como resposta as línguas naturais para as quais podemos ter um bom motivo para acreditar em um limite inferior, mesmo que ainda não exista uma prova. Por exemplo, se essa pergunta fosse sobre DTIME, eu aceitaria -CLIQUE, para uma função não decrescente f ( x ) ∈ Θ ( x ) , como uma linguagem natural que provavelmente fornece as separações necessárias, baseado em circuitos de limites inferiores de Razborov e Rossman e o n 1 - ε -inapproximability de CLICK.$f(k)$$f(x) \in \Theta(x)$$n^{1-\epsilon}$

(Editado para abordar o comentário de Kaveh e a resposta de Ryan.)

Até onde eu sei, não conhecemos essas línguas ou, se o sabemos, há uma controvérsia significativa sobre a "naturalidade" delas. Sei que essa não é realmente uma resposta satisfatória, mas posso dizer:

(a) Se você provar um tempo limite inferior para o SAT ISOLADO-k para todos os k , depois de ter, na verdade, provou P ≠ N P .$\Omega(n^k)$$k$$P \neq NP$

(b) Uma maneira que você pode esperar mostrar que k-ISOLADO SAT é um desses problemas naturais em é mostrar que k-ISOLADO O problema do SAT é difícil (no sentido formal usual de obter reduções eficientes) para N T I M E [ n k ] . De fato, é a única maneira de saber como provar esses resultados. Mas o k-ISOLATED SAT provavelmente não é difícil nesse sentido, há algumas consequências muito improváveis.$NTIME[n^{k+1}] - NTIME[n^k]$$NTIME[n^k]$

O principal motivo é que as instâncias k-ISOLADAS de SAT são solucionáveis ​​em , independentemente de k . Você pode adivinhar existencialmente a atribuição isolada e verificar universalmente (para todos os O ( log ( ∑ k i = 1 ($\Sigma_2 TIME[n]$$k$maneiras de aumentar parakbits na atribuição) que nenhuma das outras atribuições "locais" funcione.$O(\log (\sum_{i=1}^k {n \choose i}))$$k$

Aqui está a prova da parte (a). Seja ISOLATED SAT a versão do problema com fornecido como parte da entrada (em unário, por exemplo). Suponha que provemos que ISOLADO SAT requer Ω ( n k ) tempo para todos os k . Se P = N P , então Σ 2 t I M E [ n ] é em T I H E [ n c ] para algumas fixo c (a prova utiliza uma versão eficiente do teorema de Cook: Se houver um algoritmo sab executando em tempo n $k$$\Omega(n^k)$$k$$P=NP$$\Sigma_2 TIME[n]$$TIME[n^c]$$c$$n^d$, qualquer é suficiente). Mas provamos que há uma linguagem em Σ 2 T I M E [ n ] que é não em T I M E [ n k ] para cada k . Isto é uma contradição, então P ≠ N P .$c > d^2$$\Sigma_2 TIME[n]$$TIME[n^k]$$k$$P \neq NP$

Aqui está a prova da parte (b). Se todas as puderem ser eficientemente reduzidas a uma fórmula k-ISOLADO SAT (por exemplo, todas as instâncias de n bits de L sejam reduzidas a fórmulas k- ISOLADO SAT de no máximo f ( k ) n c tamanho), em seguida, N P = ⋃ K N T I H E [ n k ] ⊆ Σ 2 t I M E $L \in NTIME[n^k]$$n$$L$$k$$f(k) n^{c}$ . Isto imediatamente implica c o N P ≠ N P , mas, além disso, apenas parece muito improvável que todos N P pode ser simulado de forma eficiente dentro da hierarquia polinomial.$NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$$coNP \neq NP$$NP$