Warum ist E nicht in NP-schwer?

Question

Wieso liegt E in L0 und nicht in NP-schwer? Ich dachte immer das Halteproblem ist NP-schwer? Denn auch in Wikipedia steht "Ein klassisches Beispiel für ein Problem, das NP-schwer ist und nicht in NP liegt, ist das Halteproblem für Turingmaschinen"

Auf der Suche nach der Lösung bin ich im Internet auf eine Differenzierung des Halteproblems in "das Halteproblem", das nicht entscheidbar ist und "das spezielle Halteproblem", das semientscheidbar ist, gestoßen. Haben wir es in der Vorlesung dann also immer mit dem speziellen Halteproblem zu tun gehabt?

Answer 1

Hallo,

hier muss man vorsichtig sein!

Zunächst mal, ja, das Halteproblem ist NP-schwer. Wenn Sie es in den äußersten Bereich des NP-schwer-Kreises gemalt hätten, wäre das auch in Ordnung gewesen. Allerdings wird das nicht direkt in der Vorlesung thematisiert, weshalb wir es, um Verwirrung zu vermeiden, nur in den semientscheidbaren Bereich gemalt haben.

Wichtig ist aber richtigzustellen, dass sich "semientscheidbar" und "nicht entscheidbar" nicht ausschließen. Sowohl das allgemeine Halteproblem als auch das spezielle Halteproblem sind sowohl nicht entscheidbar als auch semientscheidbar. In der Vorlesung haben wir nur das allgemeine Halteproblem behandelt.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Comments

soll äußerster Kreis hier heißen NP-schwer geschnitten mit p (E*). Wenn ja, wieso nicht NP-schwer geschnitten mit L0?
Danke!

---

Vorweg: Ich weiß nicht, was die Übungsleiter mit "äußersten Bereich des NP-schwer-Kreises" gemeint haben.

Ich stimme dir zu, dass das Halteproblem in NP-schwer \( \cap L_0 \) liegt. Allerdings gilt \( L_0 \subset \wp (E*) \), also liegt das Haltproblem auch in NP-schwer \( \cap \wp (E*)\)  (die Mengen sind keine Ringe, sondern umfassen auch immer die innenliegenden Mengen...)

In den Hinweisen steht:

"Für NP-schwer müssen Sie nur „NP-vollständig“ und „nicht NP-vollständig“ unterscheiden."

daher wäre es bei dieser Aufgabe egal gewesen, wo in den äußeren Teil von NP-schwer du das Halteproblem eingetragen hättest. Da keine weiteren Trennlinien vorhanden sind, hätte das sonst in der Einsicht vermutlich zu Diskussionen, wo ein Problem eingezeichnet wurde, geführt :)

Gruß, Tobias (Tutor)