Complexité Computationnelle
Relations entre DT IM E, N SP ACE et Circuits Logiques
Mots Clés Définis
DTIME(t(n)) : Classe des langages décidés par une machine de Turing déterministe
en temps t(n).
NSPACE(s(n)) : Classe des langages décidés par une machine de Turing non
déterministe avec un espace limité à s(n).
Circuits Logiques : Réseaux de portes logiques qui traitent des bits en entrée
pour produire des bits en sortie.
Taille des Circuits : Mesurée par le nombre total de portes dans le circuit.
Profondeur des Circuits : Longueur du chemin le plus long depuis l’entrée
jusqu’à la sortie, mesurée en niveaux de portes.
Preuves Détaillées
1. Preuve de l’Assertion : A ∈ DT IM E(t(n)) ⇒ ∃α > 0, tels que taille(Cn ) ≤
αt(n)2
Énoncé : Si un langage A est dans DT IM E(t(n)), alors il existe une constante α > 0
telle que la taille des circuits Cn qui le reconnaissent est bornée par O(t(n)2 ).
Preuve :
1. Configuration d’une Machine de Turing : Considérons une machine de Turing
M qui décide le langage A en un temps t(n). Au maximum, M peut effectuer t(n)
opérations sur une bande ayant des dimensions proportionnelles à n.
2. État et Mémoire : Le nombre d’états que M peut avoir est |Q|, où |Q| est la
taille de l’ensemble des états. Supposons que chaque état soit représenté par un
certain nombre de bits b. Pendant le calcul, M peut lire k cellules de la bande (un
plafond de O(t(n))), donc le nombre total possible de configurations est borné par
|Q| × 2O(t(n)) .
3. Construction d’un Circuit : On peut construire un circuit qui simule cette
machine de Turing. Un circuit de simulation pour chaque étape prend en entrée
l’état actuel, le symbole courant de la bande et la position de lecture. Pour une
simulation totale de O(t(n)) étapes, la taille des circuits est donc O(t(n)2 ).
1
4. Conclusion : Nous avons montré que la taille des circuits nécessaires pour décider
de A est bornée par O(t(n)2 ), prouvant ainsi cette partie de la proposition.
2. Preuve de l’Assertion : A ∈ N SP ACE(s(n)) ⇒ ∃α > 0, tels que profondeur
αs(n)2
Énoncé : Si un langage A est dans N SP ACE(s(n)), alors la profondeur des circuits Cn
qui le reconnaissent est bornée par O(s(n)2 ).
Preuve :
1. Machine Non Déterministe : Pour un langage A dans N SP ACE(s(n)), une
machine de Turing non déterministe peut réaliser sa tâche avec s(n) cellules de
bande.
2. Configuration des États : Cette machine peut choisir parmi 2s(n) configurations
différentes à chaque étape. Cela implique qu’il existe des circuits puissants qui
simulent ces choix à chaque niveau de profondeur.
3. Structure des Circuits : En construisant des circuits à plusieurs niveaux de
profondeur, chaque niveau traite les choix de configuration. Avec s(n) niveaux, la
profondeur des circuits est bornée par O(s(n)2 ).
4. Conclusion : Ce raisonnement conclut que la profondeur peut être limitée par
O(s(n)2 ), prouvant ainsi notre assertion.
Exemple Concret
Considérons le Langage
A = {x ∈ {0, 1}∗ | x contient un nombre pair de 0}
Pour DT IM E(t(n))
Machine de Turing : Une machine peut balayer l’entrée pour compter le nombre
de zéros. Si le nombre est pair, elle accepte ; sinon, elle rejette. Cette machine
fonctionne en O(n) temps.
t(n) = n.
Circuits : On peut construire des circuits Cn de taille O(n2 ) qui simulent cette
machine en évaluant tous les états possibles et en vérifiant la parité.
Pour N SP ACE(s(n))
Machine de Turing Non Déterministe : Une telle machine peut utiliser une
seule cellule de mémoire pour compter le nombre de 0. Ici, s(n) = O(1) (espace
constant).
Circuits : On peut construire une famille de circuits Cn avec une profondeur O(1)
en vérifiant si le dernier bit est 0 et en utilisant une porte AND.
2
Résumé
Ainsi, les preuves présentées ainsi que l’exemple spécifique illustrent les relations entre les
classes de complexité, les machines de Turing et les circuits logiques. Si vous souhaitez
plus de détails ou des éclaircissements supplémentaires, n’hésitez pas à demander !