warum liegt A nicht in NP ?

Question

Ich verstehs leider nicht bei Problem A.

 

A: NP-schwer ^ entscheidbar ^ nicht NP-vollständig

 

Definition NP-schwer: Ein NP-hartes Problem ist mindestens so „schwer“ wie jedes Problem aus der Komplexitätsklasse NP. Formal heißt das, dass alle Probleme aus NP durch einen polynomiellen Algorithmus auf das betrachtete Problem reduziert werden können.

 

Müsste also NP-schwer nicht eine Teilmenge von NP sein und A somit in NP liegen?

 

Danke für die Hilfe!

Answer 1

Nein, du kannst ja "einfache" (hier: NP) Probleme immer auf "schwerere" (hier: Nicht-NP) reduzieren. Du hast ja schon geschrieben, dass ein NP-schweres Problem MINDESTENS so schwer sein muss, wie jedes Problem aus NP. Das heißt aber nicht, dass es nicht beliebig schwerer sein kann.
Dass das Problem dann auch noch in NP liegt ist eine zusätzliche Forderung, womit es dann NP-vollständig wäre.

Comments

Entweder lese ich das Inklusionsdiagramm falsch oder ich stehe gerade mächtig auf dem Schlauch.

Ich lese das doch von innen nach außen folgendermaßen (oder?):

 

- NP-vollständige Probleme sind "schwerer" oder mindestens so schwer wie die Probleme aus NP

- NP Probleme sind "schwerer" als die Entscheidbaren Probleme

- entscheidbare Probleme sind "schwerer" als die Semi-entscheidbaren

 

Wenn das stimmt, dann müsste doch ein NP-schweres Problem doch eine Teilmenge von NP sein, da sie MINDESTENS so schwer sind wie alle Probleme aus NP.

---

Wie kommst du auf diese Aussagen? Das stimmt so nicht.

- NP-vollständige Probleme sind die schwersten Probleme in NP
- Entscheidbare Probleme sind im Allgemeinen schwerer als NP-Probleme, wobei NP-Probleme eine Teilmenge darstellen
- Semientscheidbare Probleme sind im allgemeinen nochmals schwerer als entscheidbare Probleme.

Viele Grüße,
Jacob (Tutor)

Answer 2

Salopp gesagt: Im Diagramm wird es nach außen hin immer schwerer (außer bei der NP-vollst.-Menge, die man sich am Rand von NP denken könnte).

Viele Grüße

Lukas König