Hiérarchies temporelles dans DSPACE (O (s (n)))

Le théorème de la hiérarchie temporelle stipule que les machines de turing peuvent résoudre plus de problèmes si elles ont (assez) plus de temps. Tient-il d'une manière ou d'une autre si l'espace est limité asymptotiquement? Comment $\textrm{DTISP}(g(n), O(s(n)))$ au $\textrm{DTISP}(f(n), O(s(n)))$ si $\frac{f}{g}$ pousse assez vite?

Je m'intéresse particulièrement au cas où $s(n) = n$ , $g(n) = n^3$ et $f(n) = 2^n$ .

En particulier, je considérais la langue suivante: $L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps},$ $k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \}$

Cependant, $L_k$ pourrait être décidée en $n^3$ étapes à l'aide de $(k+1)n \in O(n)$ de l' espace.

Sans limiter $M$ à quatre symboles de bande et permettre ainsi de compresser $O(n)$ cellules en $n$ cellules, nous avons des problèmes d'espace lors de la simulation d'un $M$ avec trop de symboles de bande. Dans ce cas, la langue n'est plus en $\text{DSPACE}(O(n))$ . La même chose se produit lors de la définition de $k = h(|w|)$ pour certains $h$ qui peuvent être calculés assez rapidement.

Cette question est essentiellement une reformulation de ma question ici .

Modifier le résumé: modifié ( s ( n ) ) ∩ DTIME ( f ( n ) $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ en $\textrm{DTISP}(f(n), s(n))$ , cependant, je pense que l'intersection mérite également réflexion.

Il s'agit d'un problème ouvert: il est ouvert que (ou même N S P A C E ( O ( n ) ) ). On sait seulement que D T I M E ( O ( n $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$$\mathrm{NSPACE}(O(n))$ .$\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$

Cependant, sous des conjectures de complexité de calcul plausibles, il existe une hiérarchie appropriée. Par exemple, si pour chaque , CIRCUIT-SAT ∉ io- , alors où , vaut , et est constructible dans l'espace-temps.O ( 2 n - ε$ε>0$$O(2^{n-ε})$$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
$f(n)≥n$$f(n)$$2^{o(\min(n,s(n)))}$$f$

En particulier (sous l'hypothèse), l'existence d'une affectation satisfaisante pour les circuits avec entrées et taille sert comme contre-exemple à l'égalité des classes.$⌊\mathrm{lg}(f^{1+ε/2})⌋$$(\log f)^{O(1)}$

Remarques:

• CIRCUIT-SAT est au moins aussi dur que -SAT (qui est utilisé dans l'hypothèse de temps exponentiel fort).$k$

• Par convention, en CIRCUIT-SAT, est le nombre de fils d'entrée; la taille du circuit est .$n$$n^{O(1)}$

• Si l'hypothèse utilisée CIRCUIT-SAT pour les tailles de circuits quasi-linéaires, alors la borne sur peut être relâchée à . De plus, des hypothèses plus faibles / plus fortes sur la dureté de CIRCUIT-SAT donnent des hiérarchies plus faibles / plus fortes (que nous pouvons actuellement prouver).$f(n)$$O((2-ε)^{\min(n,s(n))})$

• io signifie infiniment souvent et peut être supprimé pour qui sont en un certain sens continus (y compris ).$f$$f(n)=n^a$

• Il semble probable que la hiérarchie DTISP soit suffisamment nette pour distinguer de (et peut-être ) (lorsque n'est pas trop grand par rapport à l'espace autorisé).$O(f)$$o(f/\log f)$$o(f)$$f$

• Pour distinguer de , nous avons seulement besoin de l'hypothèse la plus faible P ≠ PSPACE.$n^a$$2^n$