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

Warum ist D nicht in NP-schwer?

–1 Punkt
124 Aufrufe

Hallo,

könnten Sie mir erklären warum D nicht in NP-schwer eingezeichnet werden muss? Meine Überlegung war das D ja entweder in P, NP oder NP-schwer liegen muss da ich in Polynomialzeit Primes auf D reduzieren kann.

Oder hab ich das etwas falsch verstanden? Ich dachte, dass die Polynomialzeitreduktion nur in P, NP oder NP-schwer stattfindet?

Lg

 

Gefragt 25, Sep 2015 in 2012-H-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

Hallo,

D muss in p(E*), weil in dieser Aufgabe gefordert ist, dass die Probleme so genau wie möglich geordnet werden müssen. Die einzige Angabe die bezüglich D gegeben ist, ist dass das Problem mindestens so schwer zu lösen ist wie PRIMES. Es ist allerdings keine obere Schranke bezüglich der Komplexität gegeben, deshalb kann keine Aussage getroffen werden, ob das Problem  in NP, NP-schwer, entscheidbaren, seminentscheidbaren oder in p(E*) liegt. Deshalb müssen wir D in p(E*) einordnen. 

Grundsätzlich ist die Polynomialzeitreduktion nicht auf die Bereiche P,NP oder NP-schwer beschränkt, sondern kann durch über alle Komplexitätsklassen ausgeführt werden.

Viele Grüße,

Sebastian(Tutor)

 

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