Komplexitätstheorie ;)
-
Hallo
Ich sitze vor folgender Aufgabe:
Gegeben ist die konjunktive Normalform
(a v ¬b) ^ (¬c v d) ^ (e v f) ^ (g v ¬h).
Wie lautet die entsprechende disjunktive Normalform?Das ging noch. Aber jetzt die Frage die mir seit Tagen kopfzerbrechen macht:
-------------------
Sei T die Zeit, die der bestmögliche Algorithmus für die Ausgabe der Lösung ben
ötigen würde. Sei N die Anzahl der Bits, die zur Beschreibung der gegebenen
konjunktiven Normalform nötig sind.
Frage: Wie komplex ist das allgemeine Problem einer solchen Umwandlung bezogen
auf T im Vergleich zu N? Vergiss nicht Deine Antwort zu begründen.
-------------------
Meine Antworten die ich mir denke
Das Problem ist 2^n
Ich habe (..) v (..) ...
16 Therme für DNFKann mir wer da weiterhelfen?
Bin am verzweifelnDanke im Voraus,
mfg