Mathematische Logik: DNF finden in NP |
| 19.11.2010, 12:57 | Maks | Auf diesen Beitrag antworten » | ||
| Mathematische Logik: DNF finden in NP Ich soll unter der Annahme, dass N != NP, zeigen, dass es keinen Algorithmus in N gibt, der zu jeder aussagenlogischen Formel eine DNF findet. Meine Ideen: Ich bin etwas verwirrt. DNF ist ja eigentlich recht einfach. Man stellt eine Wahrheitstabelle auf und baut sich die Konjunktionen aus den Belegungen, die die Formel erfüllen. Scheinbar ist es nicht so einfach, oder das geht hier nicht, ich weiß es nicht, klärt mich auf 
|
||||
| 19.11.2010, 13:34 | kiste | Auf diesen Beitrag antworten » | ||
Statt N meinst du wohl P. Beachte dass DNF-SAT in linearer Zeit lösbar ist. |
||||
| 20.11.2010, 11:06 | Maks | Auf diesen Beitrag antworten » | ||
Ähh ja sorry 
Soll heißen, dass wenn ich es in P überprüfen kann, kann ich es nur in NP bilden? Und wie beweise ich das? Sorry, ich hab die Komplexitätstheorie echt noch nicht verstanden...
|
||||
| 20.11.2010, 11:39 | kiste | Auf diesen Beitrag antworten » | ||
Verstehst du selbst was du mit dem Satz sagen willst? Du sollst zeigen: Gibt es einen Algorithmus der eine Aussagenlogische Formel in DNF umwandelt in P, so ist P=NP. Kennst du denn NP-vollständige Probleme? Sonst hilft dir mein Tipp von oben ja nichts. |
||||
| 20.11.2010, 11:54 | Maks | Auf diesen Beitrag antworten » | ||
Hmm wenn du mich so fragst, vermutlich nicht. Wir haben im Skript 3-SAT und SAT als NP-vollständig angegeben. Also muss ich theoretisch mein Problem auf SAT reduzieren und hab damit gezeigt, dass es in NP liegt? |
||||
| 20.11.2010, 12:07 | kiste | Auf diesen Beitrag antworten » | ||
Warum auf SAT reduzieren? Das ist doch immer möglich, da SAT NP-vollständig ist. Du sollst mit Hilfe dieses Algorithmus um Formeln in DNF umzuwandeln SAT in P lösen. Damit wäre NP=P. Mehr kann ich wirklich nicht mehr dazu sagen, denn wenn man meine Beiträge jetzt logisch zusammenfügt hast du bereits die Lösung. |
||||
| Anzeige | ||||
|
|
||||
| 20.11.2010, 16:01 | Maks | Auf diesen Beitrag antworten » | ||
Ahh ich glaube ich habs verstanden
Ich gehe davon aus, dass es einen DNF-Algorithmus in P gibt. Damit wäre SAT auch in P (da man einfach den DNF-Algorithmus und DNF-SAT anwenden kann). Da SAT NP-vollständig ist wäre damit P = NP und da kommt der Widerspruch. Richtig? Danke!
Achja, ich habe noch ein Problem, wäre sehr nett wenn du mir da auch Tips geben könntest: Mathematische Logik: DNF-SAT Algorithmus in P |
||||
| 20.11.2010, 17:33 | kiste | Auf diesen Beitrag antworten » | ||
Genau |
||||
| 23.11.2010, 16:55 | Maks | Auf diesen Beitrag antworten » | ||
Ah jetzt wurde mir gesagt, dass es leider doch nicht so einfach ist: Denn, wenn die Ursprungsformeln die Länge n hat und die Anzahl der Variablen m <= n, dann kommt eine Formel von der Länge O(2^m * m) heraus. Wenn ich das wieder in die DNF-SAT einfüge erhalte ich eine Laufzeit von höchstens: n^k + (2^m * m)^j Was ja leider kein Polynom ist... Oder habe ich etwas falsch gemacht? Danke! |
||||
| 23.11.2010, 18:04 | kiste | Auf diesen Beitrag antworten » | ||
Das ist der naive Algorithmus zum Umwandeln in DNF. Wir nehmen doch gerade an dass der Algorithmus zum Umwandeln nur polynomiell Zeit benötigt. Damit kann auch die Formel nur polynomiell groß werden |
||||
| 23.11.2010, 18:28 | Maks | Auf diesen Beitrag antworten » | ||
...danke!
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
