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

Kategorien

1 Pluspunkt 0 Minuspunkte
385 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)
...