DNF finden nicht in N < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:13 Fr 19.11.2010 | | Autor: | cpury |
| Aufgabe | | Unter der Annahme, dass P != NP, zeige man, dass es keinen Algorithmus gibt, der für jede Formel φ in polynomialer Zeit eine Formel ψ in DNF findet, die äquivalent zu φ ist. |
Ich bin hier total verwirrt. Wie beweise ich, dass etwas nicht in N liegt? Und konkret hier: Kann ich nicht einfach eine Wahrheitstabelle anlegen und dann die Terme bilden, bei denen Wahr rauskommt? Oder geht das nicht in polynomieller Zeit?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.matheboard.de/thread.php?threadid=434771
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:22 Sa 27.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
