Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Reduktion von SAT auf eine Aufgabe (http://www.informatikerboard.de/board/thread.php?threadid=3961)
Geschrieben von apfelnymous am 04.07.2018 um 13:53:
Reduktion von SAT auf eine Aufgabe
Hallo im Anhang ist eine Aufgabenstellung und meine Lösung dazu.
Der Kommentar des Dozenten zu meiner Lösung lautet:
"Hallo,
Entscheidbarkeit bitte nicht mit NP-Problemen verwechseln. Das Sat findet hier keine Anwendung!! Das Problem Nr. 4 ist entscheidbar, da maximal 2^n Kombinationen verglichen werden müssen."
Ich verstehe nicht genau an welchem Punkt es sich von SAT unterscheidet ? Oder was müsste anders sein damit die Reduktion Sinn ergibt ??
Viele Grüße
Forensoftware: Burning Board, entwickelt von WoltLab GmbH