Cours 8 : Complexité : SPACE Hierarchy Theorem

SPACE Hierarchy Theorem

SPACE Hierarchy Theorem :

Soient $f(n), g(n)≥ \log(n)$, $f, g$ constructibles, tq

\[\lim\limits_{n \to +∞} \inf \frac{f(n)}{g(n)} = 0\]

alors il existe un langage $L$ accepté par une MT en espace $g( \vert x \vert)$ mais pas par une MT en espace $f(\vert x \vert)$.

NB :

• Si $f≤g$, alors

  \[SPACE(f(n)) ⊊ SPACE(g(n))\]
• \[NLOGSPACE ⊊ PSPACE ⊊ EXPSPACE\]

  La première inclusion vient :

  • du fait que $NLOGSPACE ⊆ PTIME$

  OU

  • de Savitch : $NLOGSPACE ⊆ SPACE(\log^2(n))$, et $SPACE(\log^2(n)) ⊊ SPACE(n)$

TIME Hierarchy Theorem :

Soient $f(n), g(n)≥ \log(n)$, $f, g$ constructibles, tq

\[\begin{cases} \lim\limits_{n \to +∞} \inf \frac{f(n) \log(f(n))}{g(n)} = 0 \\ \lim\limits_{n \to +∞} \frac{g(n)}{n} = +∞ \end{cases}\]

alors il existe un langage $L$ accepté par une MT déterministe en temps $g( \vert x \vert)$ mais par aucune MT déterministe en temps $f(\vert x \vert)$.

Ex : $f(n) = n, g(n) = n^2$

NTIME Hierarchy Theorem :

Soient $f(n), g(n)≥ \log(n)$, $f, g$ constructibles, tq

\[\begin{cases} \lim\limits_{n \to +∞} \frac{f(n+1)}{g(n)} = 0 \\ \lim\limits_{n \to +∞} \frac{g(n)}{n} = +∞ \end{cases}\]

alors il existe un langage $L$ accepté par une MT NON déterministe en temps $g( \vert x \vert)$ mais par aucune MT NON déterministe en temps $f(\vert x \vert)$.

---

Machine universelle $𝒰$ :

$𝒰$ reçoit $x=⟨M,w⟩$ et répond la même chose que $M$ sur $w$.

Th : $∃𝒰$ universelle déterministe qui prend $⟨M, w⟩$ (où $M$ est déterministe, $w$ est un mot), et qui donne le résultat de $M$ sur $w$ en temps $O(T\log T)$ si $M$ calcule en temps $T$ sur $w$.

NB : dans le grand $O$, la constante dépend de $M$ mais pas de $w$.

Difficulté : $M$ utilise un nombre quelconque de rubans de travail !

⟶ on a facilement $O(T^2 \log T)$, en concaténant tous les rubans à la suite sur le premier ruban.

Ex :

$M$

a	b	c	a
0	1	2	1

⇓

a	b’	c	a
0	1	2’	1

---

$𝒰$

a 1	b 2	c 1	a 2

⇓

b’ 0	c 1	a 2’	a 1

On veut faire “glisser” le ruban du dessus d’une case à gauche, celui du dessous d’une case à droite, le tout en temps logarithmique.

---