André Vratislavsky

Übungsgruppe vom 01.02.2000

SAT ist NP-vollständig

SAT ist die Menge der erfüllbaren Formeln der Aussagenlogik. Kennt man noch kein NP-vollständiges Problem, welches man auf SAT reduzieren kann, so muß man die NP-Vollständigkeit von SAT nachweisen, indem man überprüft, ob SAT die Definition von NP-vollständig erfüllt.
Dazu ist zu zeigen: Für den Beweis von Punkt 2 betrachten wir eine NTM, die L in polynomieller Zeit entscheidet. Der Rechenweg einer akzeptierenden Rechnung dieser beliebigen NTM für eine Eingabe x wird mit einem aussagenlogischen Ausdruck simuliert. Es wird also für eine Eingabe x ein Boolescher Ausdruck konstruiert, der genau dann erfüllbar ist, wenn x aus L ist.
Es muß nun noch nachgewiesen werden, daß dieser Ausdruck polynomielle Länge hat.
(Alles weitere siehe Vorlesung.)

Grammatiken

Bisher hatten wir Sprachen L betrachtet und die Frage gestellt, ob ein Element x in L enthalten ist. Wir haben untersucht, ob dieses Wortproblem entscheidbar, bzw. in welcher Zeit es entscheidbar ist, und uns Maschinenmodelle angesehen, die diese Entscheidung treffen sollten.
Dabei hatten wir verschiedene Sprachklassen unterschieden.

Jetzt wollen wir den Standpunkt verändern und eine Sprache L systematisch erzeugen. Dies kann mit gewissen Regelsystemen, den sogenannten Grammatiken, geschehen.

Eine Grammatik besteht im Wesentlichen aus gewissen Regeln (außerdem aus einem endlichen Alphabet, einer endlichen Menge von Variablen und einer Startvariable). (Genauer: Eine Grammatik ist ein Vierer-Tupel mit....)
Die Regeln geben im Prinzip an, wie eine Variable ersetzt werden kann. Aus allen entstehenden Rechenwegen ergibt sich die Sprache.
Hat man die Grammatik gegeben, so kann man wieder das Wortproblem stellen: Ist ein Wort x in der von einer Grammatik G erzeugten Sprache L(G) enthalten?

Chomsky-Hierarchie

Die Formalen Sprachen lassen sich in der Chomsky-Hierarchie wie folgt einteilen:

(Variablen sind GROSS geschrieben, Terminalzeichen klein geschrieben.)
Typ Regeln l->r (Beispiele) Beispiel Sprachen Maschine
Typ0 keine Einschränkung rekursiv aufzählbare NTM, TM
Typ1 ABC->AxyC SAT, 3-SAT,
{anbncn|n>1}		 kontextsensitive NTM mit linearem Speicherbedarf
Typ2 A->AxyC {anbn|n>1},
Palindrome, {w|#0=#1}		 kontextfreie
Typ3 A->aB, A->epsilon reguläre NFA, DFA

Genaueres siehe Vorlesung.