Zeige: Algo existiert nicht < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:56 Di 23.11.2010 | | Autor: | Manu87 |
| Aufgabe | | Unter der Annahme, dass $P [mm] \not= [/mm] NP$, zeige man, dass es keinen Algorithmus gibt, der für jede Formel [mm] \phi [/mm] in polynomialer Zeit eine Formel [mm] \psi [/mm] in DNF findet, die äquivalent zu [mm] \phi [/mm] ist. |
Alter falter... ich muss gestehen mit diesen Übungen kann ich einfach nichts anfangen...
Ich hoffe einige kluge Köpfchen können mir helfen , während ich weiter verzweifelt nach einer Lösung suche...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:20 Mi 24.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
