Satz von Immerman und vszlepcsényi – Wikipedia

Le Satz von Immerman und Velepcsényi est une phrase de la théorie de la complexité et déclare que les classes de complexité spatiale non éterministe sont terminées sous la formation du complément. En particulier, la classe NL (lieu de logarithmique non éterministe) est terminée sous la formation du complément.

Pendant longtemps, comme pour les classes de complexité temporelle non éterministe, il a été supposé que NL n’était pas achevé en vertu du complément qu’en 1988 a toujours fourni des preuves. Pour cela, les deux ont reçu le prix Gödel (1995).

Peut être

${displayStyle s: mathbb {n} rightarrow mathbb {n}}$

une fonction monotone avec

${DisplayStyle s (n) dans Omega (log (n))}$

. Ensuite, ce qui suit s’applique:

${DisplayStyle {textsf {nspace}} (s (n)) = {textsf {co-nspace}} (s (n))}$

En particulier, s’applique alors

${DisplayStyle {textsf {nl}} = {textsf {co-nl}}}}$

.
Mais cela s’applique également à

${DisplayStyle {textsf {nl}} = {textsf {co-nl}}}}$

Avec la technologie de rembourrage le théorème pour tout le monde

${DisplayStyle s (n) dans Omega (log (n))}$

suit.

Les preuves utilisent la technologie des preuves du comptage inductif (non déterministe).

Remarques préliminaires [ Modifier | Modifier le texte source ]]

Peut être

${displayStyle l: = l (g)}$

Une langue au-dessus de la grammaire de type 1

${displayStyle g: = (n, sigma, delta, s)}$

Avec les symboles habituels pour non-terminal

${displaystyle n}$

, Terminal

${DisplayStyle Sigma}$

, Règles de production

${DisplayStyle Delta}$

Et le symbole de début

${DisplayStyle S}$

.
Alors c’est pour un mot

${displaystyle win Sigma ^ {ast}}$

Le graphique

${displayStyle graph_ {| w |}: = ((Sigma Cup n) ^ {leq | w |}, alpha rightarrow _ {g} bêta)}$

le graphique que tous les ensembles se trouvent avec une longueur au plus sur la longueur de

${displayStyle in}$

contient, par lequel le graphique a un bord entre deux ensembles de mouvement lorsqu’il s’agit d’une production en

${displaystyle g}$

donne.
En particulier, le graphique contient les deux

${DisplayStyle S}$

ainsi que

${displayStyle in}$

vous-même et cela s’applique que

${displaystyle win l}$

Exactement quand il y a un chemin de

${DisplayStyle S}$

après

${displayStyle in}$

dans ce graphique.

S’il est maintenant possible de construire une machine de Turing non détéministe et linéaire qui accepte exactement quand elle Non Chemin de

${DisplayStyle S}$

après

${displayStyle in}$

la preuve est fournie.

Non-compétence [ Modifier | Modifier le texte source ]]

Il a d’abord été supposé que le nombre

${displaystyle n}$

le nœud réalisable de

${DisplayStyle S}$

est connu (nous reportons le calcul de

${displaystyle n}$

sur plus tard).
Ensuite, l’algorithme suivant résout le non-acabilité d’atteindre.

Graphique donné

${displayStyle g = (v, e)}$

, Le nœud de démarrage

${DisplayStyle S}$

, Node cible

${displayStyle t}$

et nombre de nœuds accessibles

${displaystyle n}$

.

1. Compteurs initialisés
   ${displayStyle c: = 0}$

   

2. Pour chaque nœud
   ${Displaystyle vin v}$

   :

   • Conseiller non déterministe, si
     ${DisplayStyle V}$

     depuis

     ${DisplayStyle S}$

     peut être atteint et si la réponse est positive:

3. Chutes
   ${DisplayStyle C$

   , rompre avec Non off, sinon donner et hors de.

Ni

${displaystyle n}$

toujours

${DisplayStyle C}$

peut plus grand que

${displayStyle | v |}$

le sien et consommer (codé binaire) rien de plus que

${DisplayStyle Log (| v |)}$

Espace de stockage.
L’algorithme garantit que tout le monde

${displaystyle n}$

Nootes que de

${DisplayStyle S}$

sont accessibles, à être répertoriés et uniquement acceptés si

${displayStyle t}$

n’était aucun de ces nœuds.

Compter inductif [ Modifier | Modifier le texte source ]]

Maintenant, seul le nombre précédemment inconnu reste

${displaystyle n}$

pour déterminer les nœuds accessibles. L’idée est le numéro

${displaystyle n_ {i}}$

pour calculer le nœud, qui est au plus

${displayStyle i}$

Les étapes sont accessibles. Tu pars

${displayStyle i}$

Puis comptez inductif et utilisez-le

${DisplayStyle n = n_ {| v |}}}$

est applicable. L’algorithme fonctionne comme suit:

1. Initialiser
   ${displayStyle n_ {0}: = 1}$

   (Le nœud de démarrage n’a pas besoin d’une étape pour être atteint)

2. Pour chaque nombre d’étapes
   ${displayStyle i = 1, points, | v |}$

   :

   1. Initialiser
      ${displayStyle n_ {i}: = 0}$

      .

   2. 
      ${DisplayStyle Star}$

      Pour chaque nœud

      ${Displaystyle vin v}$

      :

      1. Initialiser un compteur
         ${displaystyle c:=0}$

         

      2. Pour chaque nœud
         ${displaystyle uin V}$

         :

      3. Chutes
         ${displaystyle c$

         , casser le calcul

3. Cadeau
   ${displaystyle n_ {| v |}}$

   retour.

Depuis l’algorithme seulement trois points (

${DisplayStyle c, n_ {i}, n_ {i-1}}}$

) En même temps, il peut être réalisé avec un espace de stockage logarithmique.
Des preuves formelles de l’exactitude sont laissées au lecteur intéressé. La note suivante est l’idée de preuve:

${displaystyle n_ {i}}$

Sera exactement alors alors pas incrémenté lorsque tous les nœuds avec une distance plus petite que

${displayStyle i}$

et aucun autre directement (c’est-à-dire dans un maximum d’une étape) n’a pu être trouvé.

La preuve [ Modifier | Modifier le texte source ]]

Maintenant, seuls les deux algorithmes doivent être combinés.

1. Calculer
   ${displaystyle n}$

   pour

   ${displayStyle g: = graph_ {| w |}}$

   et

   ${displayStyle s: = s}$

   compter par le comptage inductif.

2. Utiliser la non-compétence pour
   ${displayStyle g: = graph_ {| w |}, s: = s}$

   et

   ${displayStyle t: = w}$

   Avec précédemment calculé

   ${displaystyle n}$

   .

Une telle machine Turing accepte exactement s’il n’y a pas de chemin de

${DisplayStyle S}$

après

${displayStyle in}$

Et comme les deux algorithmes partiels n’ont besoin que d’espace de stockage logarithmique, la preuve est terminée.

Publications originales:

Manuels: