Moin da draußen,

könnte mir bitte irgendjemand den Unterschied zwischen NP schwer und NP vollständig nochmal erklären. In den letzten beiden Vorlesungen bin ich irgendwie ausgestiegen.
Wäre super … danke

Fitzi

NP schwer - Ein Problem ist NP schwer wenn jedes Problem aus NP sich darauf in Polynomialzeit reduzieren laesst
NP vollstaendig - Das Problem ist NP schwer UND zusaetzlich in NP

D.h. ein Problem dass NP schwer ist muss nicht zwingend in NP liegen, es kann z.B. noch schwieriger als NP sein. Aber alle aus NP muessen sich drauf reduzieren lassen.
Bei NP vollstaendig muss das Problem selber auch in NP liegen - es beschreibt somit eine der schwersten Probleme in NP, da sich ja alle aus NP drauf reduzieren lassen.

Kleiner Zusatz noch: Beispiele für NP-schwierige Probleme, die nicht NP-vollständig sind, sind z.B.
alle Probleme, die für "schlimmere" Komplexitätsklassen als NP vollständig sind.

Beispielsweise sind PSPACE-vollständige Probleme (NP \subseteq PSPACE) NP-schwierig.

(Obiges "die nicht NP-vollständig sind" ist zu lesen als "aller Voraussicht nach nicht NP-vollständig". Gilt
nämlich wider erwarten so etwas wie NP = PSPACE, dann sind die PSPACE-vollständigen Probleme plötzlich einfach nur noch NP-vollständig.)

Frank :)

P = NP, gilt für P = 0 oder N = 1 *scnr*