Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Beweis von Immerman und Szelepcsényi
Autor
Universität/Hochschule Beweis von Immerman und Szelepcsényi
baxbear
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.11.2012
Mitteilungen: 83
Wohnort: Deutschland, Brandenburg
  Themenstart: 2021-05-02

Hallo liebes Forum, ich habe mir für diesen Sonntag einen schönen Beweis rausgesucht, verstehe ihn aber leider nicht vollständig bzw. die entsprechende Beweisskizze auf Wikipedia: https://de.wikipedia.org/wiki/Satz_von_Immerman_und_Szelepcs%C3%A9nyi Mein Problem ist der Schritt Rate nichtdeterministisch einen Pfad von $s$ nach $v$ der Länge höchstens $|V|$ und falls der Pfad falsch war oder nicht zu $v$ führt, brich mit nein ab, Warum kann ich aus der Nicht-Existenz des Pfades darauf schließen, dass ein Wort akzeptiert werden würde? Also es im Konfigurationsgraphen erreichbar sein muss. Irgendwie hängt es damit zusammen, dass ich vorher eine positive Antwort auf die Frage der Erreichbarkeit hatte. Es aber keinen Pfad $\leq |V|$ gab. Trotzdem verstehe ich nicht, wie man aus der Nicht-Existenz auf die Akzeptanz von w schließen kann.


   Profil
baxbear
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.11.2012
Mitteilungen: 83
Wohnort: Deutschland, Brandenburg
  Beitrag No.1, vom Themenstarter, eingetragen 2021-05-08

Ist die Antwort auf meine Frage so simpel/trivial, dass ich einfach nur blind bin bzw. irgendwie einen Knoten im Kopf habe und es schwer ist mehr Details zur Verfügung zu stellen?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2717
  Beitrag No.2, eingetragen 2021-05-08

\quoteon(2021-05-02 16:42 - baxbear im Themenstart) Warum kann ich aus der Nicht-Existenz des Pfades darauf schließen, dass ein Wort akzeptiert werden würde? Also es im Konfigurationsgraphen erreichbar sein muss. \quoteoff Ich glaube, du missverstehst die Ergebnisse "ja" und "nein" der dort beschriebenen nichtdeterministischen Turingmaschine. * Ein "ja" bedeutet, dass die Maschine einen Lauf durchgeführt hat, aus dem folgt, dass $t$ von $s$ aus nicht erreichbar ist. * Ein "nein" bedeutet, dass die Maschine einen Lauf durchgeführt hat, aus dem das nicht folgt. Es bedeutet nicht, dass aus diesem Lauf das Gegenteil (also dass $t$ von $s$ aus erreichbar ist) folgt. --zippy


   Profil
baxbear hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]