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!
 

 

warum liegt A nicht in NP ?

–1 Punkt
63 Aufrufe

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!

Gefragt 26, Nov 2014 in BER-AA von uafjv uafjv Tutor(in) (167,840 Punkte)  

2 Antworten

0 Punkte
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.
Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,840 Punkte)  
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)
0 Punkte
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
Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,840 Punkte)  
...