Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in 2010-N-04

b): (3) - R min. in NP?

Fri, 25 Sep 2015 12:57:20 +0000

Hallo,

gilt bei (b) bei Aussage (3) nicht, dass R mindestens in NP liegt? (also zumindest nicht in P)

Danke!

b): (3) - R auch aus P?

Fri, 25 Sep 2015 12:55:13 +0000

Dürfte R auch aus der Klasse P sein oder muss R mindestens aus der Klasse NP sein?

Danke

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

Fri, 25 Sep 2015 12:53:26 +0000

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.