a): (2) Halteproblem - NP-schwer aber nicht mehr in NP?

Question

In der Muster Lösung ist für Aufgabenteil (2) angegeben, dass alle Probleme aus Aufgabenteil (4) hier eine richtige Lösung wären.

Das stimmt mMn nicht ganz, da Augabenteil (4) ja alle NP-schweren Probleme aufzählt und mit dem Halteproblem ja auch explizit ein Problem nennt, das zwar NP-schwer ist, aber nicht mehr in NP liegt.

 

Answer 1

Ja, da haben wir uns wohl vertan... Das muss geändert werden.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

 

Answer 2

Was das Halteproblem angeht, kann ich dir nur zustimmen, ich denke, es sind die restlichen aufgeführten Probleme SAT, 3-SAT, CLIQUE gemeint, die alle NP-vollständig sind. Ich werde das an die Übungsleiter weiterleiten.

Tobias (Tutor)