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

Schöne Ferien!
 

 

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

+1 Punkt
228 Aufrufe

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.

 

Gefragt 25, Sep 2015 in 2010-N-04 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

0 Punkte
 
Beste Antwort

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

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
0 Punkte

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)

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...