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

Question

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

Danke

Answer 1

Falls \( Q \in P\) gilt (d.h. Q ist ein relativ leichtes Problem), dann kann auch \( R \in P \)gelten (muss aber nicht, man leichte Probleme auch auf sehr schwierige (Halteproblem etc) reduzieren...).

Um es klar zu stellen: \(Q \in P\) kann man NICHT aus den gegebenen Informationen schließen (aber auch nicht ausschließen)

Gruß,

Tobias (Tutor)