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!
 

 

Kann ein Problem X aus P auch NP-schwer sein ?

+1 Punkt
31 Aufrufe
Hallo,

ich habe eine grundsätzliche Verständnisfrage zu den Klassen P und NP-vollständig.

Kann ein Problem X aus der Klasse P NP-schwer sein ?

Denn wenn dem so ist, dann dürfte die Schnittmenge aus P und NP-vollständig ja nicht leer sein. Wir wissen ja, dass P eine  Teilmenge von NP ist. Folglich ist die erste Voraussetzung erfüllt.
Gefragt 17, Jul 2017 in BER-AL von Anonym  

Eine Antwort

0 Punkte
 
Beste Antwort
Wenn das der Fall wäre, würde $P=NP$ gelten. Oder anders gesagt, wenn $P=NP$ wäre, wären alle Probleme aus $P$ auch $NP$-schwer bzw. dann natürlich sogar  $NP$-vollständig (bis auf zwei, siehe Komplexitätskapitel in unserem Lehrbuch).

Wir gehen heute von $P \neq NP$ aus, also auch davon, dass es keine $NP$-schweren Probleme in $P$ gibt.
Beantwortet 17, Jul 2017 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 19, Jul 2017 von Marlon Braun
...