I 252
Labyrinth/Poundstone: Labyrinthe nehmen das Grundproblem der Schlussfolgerung voraus, nämlich die Frage danach, wie man ein Paradox erkennt. - (NP-vollständig).
>
Schlussfolgerungen, >
Paradoxien, >
Erkennen.
"Rechtsregel": Die Rechtsregel in Labyrinthen wird durch Inseln überwunden und ist daher ineffizient.
Lösung: Tremaux: einen Faden abrollen, bei einer Sackgasse zum letzten Knoten zurück gehen, Sackgassen markieren. - Zwei Brotkrumen markieren alte Sackgassen. - Bei alten Knoten den noch nicht gewählten Weg wählen.
I 259
Das führt dazu, entfernte Gebiete zuerst zu erforschen.
I 267
"Problem des längsten Wegs": Gibt es einen einfachen Weg? - Probieren führt nicht direkt zum kürzesten Weg. - Kein intelligenter Algorithmus ist verfügbar.
I 270
NP-vollständig/Poundstone: Die Antworten sind leicht zu überprüfen! - Bsp Labyrinth: Der richtige Weg ist vielleicht nur zwei Knoten entfernt, aber man musste viele Kombinationen durchprobieren.
>
Überprüfung, >
Verifikation, >
Bestätigung.
I 282
Poundstone: Es ist bewiesen, dass NP-Probleme nicht mit dem Computer gelöst werden können.
I 274
Kombination/Permutation/Kombinatorik: P: Polynomialfunktion: n² - Bsp Puzzle mit 5000 Teilen, ist lösbar.
NP : Exponentialfunktion. 2
n.
Bsp Ein Labyrinth mit 5000 Wegen, ist nicht lösbar.
Polynomialfunktionen allgemein: schwer lösbar.
NP: "nichtdeterministisch polynomialzeitlich vollständig".
I 276
Bisher gibt es keinen Beweis, dass NP-Probleme nicht in Polynomialzeit lösbar sind. - Aber wir haben keine empirischen Belege.
Der Prozess der logischen Inferenzen ist selbst ein NP-Problem. - Unsere Schlüsse über die Welt sind begrenzt.
I 281
Der Kettenschluss, die eigentliche Grundlage unseres Wissens, kann in Polynomialzeit erkannt und auf Widersprüche überprüft werden. - (Das ergibt Listen; als Labyrinth aber nicht begehbar).
>
Wissen, >
Widersprüche, >
Widerspruchsfreiheit.
