KNF-SAT
-
Hallo,
KNF-SAT ist ja bekanntlich ein NP-vollständiges Problem. Nun kann eine KNF-Formel ja durch folgende Variablen charakterisiert werden:
- k = max. Anzahl an Literalen pro Klausel
- n = Anzahl der atomaren Formeln in der KNF-Formel
- m = Anzahl der Klauseln in der KNF-FormelEs heißt ja, dass man durch Ausprobieren aller Belegungen für die Formel eine Komplexität von O(2^n) erreicht. Nun ist ja das Problem in NP, was ja anscheinend daran liegt, dass man für eine einzige Belegung in Polynomialzeit entscheiden kann, ob sie die Formel erfüllt oder nicht.
Meine Frage ist nun, warum hier m aus dem Spiel gelassen wird. Schließlich kann es in einer beliebigen KNF-Formel bis zu m = 2^n verschiedene Klauseln geben, wieso kann also eine nichtdeterministische Turingmaschine eine möglicherweise exponentiell in n wachsende Eingabe in Polynomialzeit verarbeiten (von nicht-KNF-Formeln mal ganz zu schweigen)?(Für k-KNF-SAT mit beliebigem, aber festem k sieht das aus meiner Sicht schon anders aus, schließlich wächst die maximale Anzahl der verschiedenen Klauseln hier nur in O(n^k)).
-
Die Laufzeit wird nicht abhängig von n gemessen, sodnern abhängig von der Größe der Eingabe. Wenn Du also sehr viele klauseln hast, erlaubt das automatisch auch entsprechend mehr Laufzeit. Wenn Du 2^n Klauseln hast, dann ist eine laufzeit von O(2^n) zum beispiel linear (!) in der Eingabegröße.
-
Danke, das klingt sinnvoll
-
Eine Frage ist mir doch noch gekommen: Wenn ich einfach alle Belegungen durchprobiere, dann ist dieser Algorithmus ja linear in der Eingabelänge, dafür aber exponentiell in der Anzahl der atomaren Formeln. Was ist nun also relevant für die exponentielle Laufzeit?
-
wxSkip schrieb:
Eine Frage ist mir doch noch gekommen: Wenn ich einfach alle Belegungen durchprobiere, dann ist dieser Algorithmus ja linear in der Eingabelänge
Ne,exponentiell. Wie kommst du darauf?
//edit ahso!
Du lässt dich hier von einem Snnderfall beeindrucken. Die Aussage ist aber auf den worst-case gezogen: bei einer Eingabe der Länge n, was ist das die Laufzeit des schwersten mit dieser Eingabe zu erzeugenden Problems?