Was ist die Klasse P umgangssprachlich
Die Klasse der effizient lösbaren Probleme
Wann ist eine Sprache A polynomiell überprüfbar?
Wenn es einen Algorithmus V gibt, sodass für alle Eingaben w gilt:
=> Ziel: NTM in Polynomialzeit konstruieren
Wie ist die Klasse NP definiert?
NTIME(n^O(1))
Satz 11 (np - polynomiell)
NP <==> polynomiell überprüfbar
Beweis von Satz 11 (NP <==> polynomiell überprüfbar
es gibt DTM V mit Laufzeit n^k und EIngabe <w,x> und |w| = n
Mit NTM DTM Pfad erraten -> Alle möglichen Pfade durchgehen und auf Akzeptanz prüfen
Andere Richtung:
Simuliere M mit eingabe w und x als Wahlmöglichkeit
if xi = 0, dann erste Wahlmöglichkeit
if xi = 1, dann zweite …
…
bis xi = c-1
if Simulation akzeptiert.. fertig
C ist Anzahl Wahlmöglichkeiten
Was ist die Klasse NP umgangssprachlich?
Klasse der effizient überprüfbaren Probleme
In welcher Klasse liegt CLIQUE? Was ist CLIQUE?
NP
CLIQUE{<G,k>} -> der Graph G hat als Teilgraphen einen vollständigen Graphen mit k Knoten
In welcher Klasse liegt HAMPATH? Was ist das?
HAMPATH{G,s,t} Gerichteter Graph, der Hamiltonschen Pfad von s nach t besitzt (Pfad mit jedem Knoten 1x)
Welches Indiz, ob ein Problem in NP liegt
Existenzquantor im Problem definiert -> es existiert ein Pfad…
In welcher Klasse liegt SUBSET-SUM? Was ist das?
SUBSET-SUM{<x1,…xn,t| es gibt eine Menge mit beliebigen xi, die in Summe t ergeben}
Was ist das SAT Problem? Zu welcher Klasse gehört es?
Es existiert eine aussagenlogische erfüllbare Formel
Reduzierbarkeit Polynomialzeit
Zwei Sprachen A,B können aufeinander reduziert werden, falls es eine Funktion gibt, die mit Eingabe aus A Wörter aus B erzeugen kann in Polynomialzeit. Dann sagt man Reduktion von A auf B:
Satz 12 Reduzierbarkeit
Sei
, dann gilt
Satz 13
reflexiv A pm auf A -> klar
transitiv
A pm auf B und
B pm auf C
Also A pm auf C
Zuletzt geändertvor einem Jahr
