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.


Leave a comment