Hallo zusammen,

Folgendes verstehe ich nicht. Weiss nicht, ob dies der Richtige Ort ist.


Gemäss Lösung sind folgende Aussagen korrekt: 2,4,7,8,10,12

1) Stimmt nicht, da <=m <=p sind nicht das gleiche. Da <= in polytime gelöst wird während <=m in einer unbekannten Zeit gelöst wird.
2) Warum ist empty satisfiable?
3)Verstehe ich nicht
4) Aus jedem DFA kann man einen NFA und umgekehrt erstellen
5) Es würde nur stimmen, wenn A >= B wäre oder? Es liegt am Zeichen, dass die Aussage nicht stimmt oder?
6) Nicht jede Sprache ist decidable oder? Warum ist diese Aussage falsch?
7) Wenn A in polytime gelöst werden kann, dann kann man auch B in polytime lösen.
8) warum falsch? A wird doch in polytime gelöst oder nicht?
9) A und B müssen in NP complete sein, damit es in P ist?
10) Sollte doch korrekt sein oder nicht? Warum?
11) Sollte doch stimmen nicht?
12) Verstehe ich nicht

Danke für eure Unterstützung!