True/False Theoretische Informatik

Aufrufe: 910     Aktiv: 13.07.2021 um 23:08
1

Hallo zusammen

Wieso ist die erste richtig und die zweite Aussage falsch?

enter image description here

Diese Frage melden
gefragt

Student, Punkte: 66

 
Kommentar schreiben
1 Antwort
1

Hi sayuri,

nach dem Satz von Cook und Levin ist das SAT-Problem NP-vollständig. Aus der Prämisse P=NP folgt dann, dass SAT in P liegt.

Die 2. Aussage behandelt das allgemeine Halteproblem, das nicht entscheidbar ist. Also kann es auch nicht in Polynomzeit auf einer DTM berechnet werden.

Diese Antwort melden
geantwortet

Student, Punkte: 40

 

Kommentar schreiben