Existe-t-il un théorème de la hiérarchie temporelle pour PH?

Est-il vrai qu'il y a des problèmes dans la hiérarchie polynomiale qui peuvent être résolus dans le temps (par une machine de Turing alternée à un certain niveau de la hiérarchie polynomiale) qui ne sont pas résolus dans à aucun niveau de la hiérarchie polynomiale? En d'autres termes - existe-t-il un théorème de hiérarchie temporelle pour la hiérarchie polynomiale comme il en existe pour P et NP? Si tel est le cas, une référence serait formidable. $O(n^k)$ $O(n^{k-1})$

La difficulté que j'ai rencontrée est que la machine de simulation, lorsqu'elle simule des machines à tous les niveaux de la hiérarchie, n'est pas à un niveau distinct de la hiérarchie. Ce qui conduit à une question connexe - à quelle classe appartient une telle machine de simulation? Y a-t-il un sens à définir une classe avec des alternances (ou / )? $O(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Joseph
la source

L'utilisation d'un nombre linéaire d'alternances vous donne PSPACE, car la formule booléenne quantifiée est complète avec PSPACE.

Derrick Stolee

Réponses:

Oui. Par exemple, les preuves habituelles du théorème de la hiérarchie temporelle (en simulant directement des machines arbitraires) peuvent être utilisées pour montrer que pour tout , n'est pas un sous-ensemble de . La raison du passage de à $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$ est que, dans cet argument de diagonalisation, nous devons faire "l'opposé" de la machine que nous simulons, donc nous devons exécuter en mode universel lorsque la machine de simulation est en mode existentiel, et vice-versa.

Vous pouvez également obtenir un résultat comme celui-ci sans passer de à : pour chaque , n'est pas un sous-ensemble de . Cela peut être fait en utilisant la preuve de la hiérarchie du temps due à Zak (référence: " A Turing machine time hierarchy ", Theoretical Computer Science 26 (3): 327--333, 1983). Pour une référence explicite à cette version du théorème de la hiérarchie temporelle, voir Dieter van Melkebeek $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$ « A Survey of Lower Bounds for Satisfiability and Related Problems » (disponible sur sa page d'accueil).

Ryan Williams
la source

Cette réponse démontre très clairement l'existence d'un théorème de hiérarchie temporelle pour chaque niveau distinct de la hiérarchie. Cela n'indique pas immédiatement la présence d'un tel théorème pour PH dans son ensemble.

Joseph

Votre question plus forte sera difficile à résoudre par l'affirmative; cela impliquerait

. Supposons qu'il y ait un

et un langage

dans

qui ne soit pas dans

pour chaque

. Alors

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

. En effet, chaque langue

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

est en

pour certains

fonction de

(par un argument de type théorème de Savitch). Donc, si

alors en fait, chaque langue dans

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

est dans

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

pourcertains

, contradictoire avec ce que vous voulez montrer.

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

Ryan Williams

La réponse à la question révisée (révision 4 de la question) est non. Si un problème de décision L est résoluble en temps O ( n ^k ) par une machine ∑ _i P, alors L peut être résolu en temps linéaire par une machine de Turing avec l'oracle pour L , qui est une machine ∑ _{i +1} P. Par conséquent, ∑ _i TIME [O ( n ^k )] ⊆ Σ _{i +1} TIME [O ( n )].

Tsuyoshi Ito
la source

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

N P \neq c o N P

$NP \neq coNP$

N P = c o N P

$NP = coNP$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for every

j, k

$j,k$ , let

O (n^{c})

$O(n^c)$ be the running time of some nondeterministic algorithm for Tautology. Then we have

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$ , where the first inclusion is by assumption and the second inclusion follows from a standard simulation argument. This is a contradiction.

Ryan Williams

@Ryan: The definition I used is: L∈ΣiTIME[t(n)] iff there exist a language O∈Σ(i−1)P and a nondeterministic t(n)-time Turing machine with the oracle for O that recognizes L. I thought that this is the standard definition, but I do not have any reference to back up my claim. What is the definition you are using?

Tsuyoshi Ito

The definition is:

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$ iff there is a linear time predicate

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$ such that

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$ is true.

Ryan Williams

@Ryan: Ok, I did not know that definition. If that is what the asker wanted to ask, my answer does not apply.

Tsuyoshi Ito