Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Warum ist E nicht in NP-schwer?

+1 Punkt
334 Aufrufe
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?
Gefragt 25, Sep 2015 in 2012-H-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte
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
Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
...