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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
540 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?
in 2012-H-05 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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
von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
soll äußerster Kreis hier heißen NP-schwer geschnitten mit p (E*). Wenn ja, wieso nicht NP-schwer geschnitten mit L0?
Danke!
0 0
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)
...