Hallo!
Kann mir mal jemand den Unterschied zwischen NP - vollständig und NP - hart erklären?
Florian
NP-Hart heisst, dass man jedes Problem in NP darauf reduzieren kann.
NP-vollstaendig heisst zusaetzlich, dass das Problem selbst in NP
ist.
So z.B. ist Q-Sat, das PSpace-Vollstaendig ist natuerlich NP-hart, aber nicht NP-vollstaendig.
MfG
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]