Existe-t-il des séparations naturelles dans la hiérarchie temporelle non déterministe?

Le théorème original de la hiérarchie temporelle non déterministe est dû à Cook (le lien est à S. Cook, Une hiérarchie pour la complexité temporelle non déterministe , JCSS 7 343–353, 1973). Le théorème stipule que pour tout nombre réel et , si alors NTIME ( ) est strictement contenu dans NTIME ( ).r 2 1 ≤ r 1 < r $r_1$$r_2$$1 \le r_1 \lt r_2$ n r $n^{r_1}$$n^{r_2}$

Un élément clé de la preuve utilise une diagonalisation (non spécifiée) pour construire un langage de séparation des éléments de la classe plus petite. Non seulement il s'agit d'un argument non constructif, mais les langues obtenues par diagonalisation ne fournissent généralement aucun autre aperçu que la séparation elle-même.

Si nous voulons comprendre la structure de la hiérarchie NTIME, il faut probablement répondre à la question suivante:

Existe-t-il un langage naturel en NTIME ( ) mais pas en NTIME ( )? n $n^{k+1}$$n^k$

Un candidat pourrait être k-ISOLATED SAT , ce qui nécessite de trouver une solution à une formule CNF sans aucune autre solution dans la distance de Hamming k. Cependant, ce qui prouve la limite inférieure semble est difficile, comme d' habitude. Il est évident que la vérification d'une k-ball de Hamming est exempte de solutions potentielles "devrait" nécessiter différentes affectations à vérifier, mais ce n'est en aucun cas facile à prouver . (Remarque: Ryan Williams souligne que cette borne inférieure pour ISOLATED SAT prouverait en fait P ≠ NP, donc ce problème ne semble pas être le bon candidat.)$\Omega(n^k)$$k$

Notez que le théorème est inconditionnel, indépendamment des séparations non prouvées telles que P vs NP. Une réponse affirmative à cette question ne résoudrait donc pas P vs. NP, à moins qu'elle ne possède des propriétés supplémentaires comme ISOLATED SAT ci-dessus. $k$ Une séparation naturelle de NTIME aiderait peut-être à éclairer une partie du comportement "difficile" de NP, la partie qui tire sa difficulté d'une séquence ascendante infinie de dureté.

Étant donné que les limites inférieures sont difficiles, j'accepterai comme réponse des langues naturelles pour lesquelles nous pouvons avoir une bonne raison de croire à une limite inférieure, même s'il n'existe pas encore de preuve. Par exemple, si cette question concernait DTIME, alors j'aurais accepté -CLIQUE, pour une fonction non décroissante , comme un langage naturel qui fournit probablement le nécessaire séparations, basées sur les bornes inférieures du circuit de Razborov et Rossman et l' inapproximabilité de CLIQUE.f ( x ) ∈ Θ ( x ) n 1 - $f(k)$$f(x) \in \Theta(x)$$n^{1-\epsilon}$

(Modifié pour répondre au commentaire de Kaveh et à la réponse de Ryan.)

Pour autant que je sache, nous ne connaissons pas de telles langues, ou si nous le faisons, il y a une controverse importante sur leur "naturalité". Je sais que ce n'est pas vraiment une réponse satisfaisante, mais je peux dire:

(a) Si vous prouvez une limite inférieure de temps pour k-ISOLATED SAT pour chaque , alors vous avez en fait prouvé .k P ≠ N $\Omega(n^k)$$k$$P \neq NP$

(b) Une façon dont vous pourriez espérer montrer que k-ISOLATED SAT est l'un de ces problèmes naturels dans est de montrer que le problème k-ISOLATED SAT est difficile (au sens formel habituel de réductions efficaces) pour . En fait, c'est la seule façon dont nous savons prouver ces résultats. Mais k-ISOLATED SAT n'est probablement pas difficile dans ce sens, il y a des conséquences très improbables.N T I M E [ n k$NTIME[n^{k+1}] - NTIME[n^k]$$NTIME[n^k]$

La raison principale est que les instances k-ISOLATED SAT sont résolubles dans , indépendamment de . Vous pouvez deviner existentiellement l'assignation isolée, puis vérifier universellement (pour toutes les façons de retourner jusqu'à bits dans l'affectation) qu'aucune des les autres missions "locales" fonctionnent.$\Sigma_2 TIME[n]$$k$$O(\log (\sum_{i=1}^k {n \choose i}))$$k$

Voici la preuve de la partie (a). Soit ISOLATED SAT la version du problème avec donné dans le cadre de l'entrée (en unaire, disons). Supposons que nous prouvons que SAT ISOLÉ nécessite un temps pour tout . Si , alors est dans pour certains fixes (la preuve utilise une version efficace du théorème de Cook: s'il existe un algorithme SAT fonctionnant au temps , alors tout suffit). Mais nous avons prouvé qu'il y a un langage dans qui n'est pas dans pour chaque$k$$\Omega(n^k)$$k$$P=NP$$\Sigma_2 TIME[n]$$TIME[n^c]$$c$$n^d$$c > d^2$$\Sigma_2 TIME[n]$$TIME[n^k]$$k$. Ceci est une contradiction, donc .$P \neq NP$

Voici la preuve de la partie (b). Si chaque peut être efficacement réduit à une formule k-ISOLATED SAT (par exemple, toutes les instances de bits de sont réduites à -ISOLATED SAT formules d'au plus taille) puis . Cela impliquerait immédiatement , mais de plus, il semble très improbable que tout puisse être simulé si efficacement dans la hiérarchie polynomiale.n L k f ( k ) n c N P = ⋃ k N T I M E [ n k ] ⊆ Σ 2 T I M E [ n c + 1 ] c o N P ≠ N P N $L \in NTIME[n^k]$$n$$L$$k$$f(k) n^{c}$$NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$$coNP \neq NP$$NP$