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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
114 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!

in BER-AA von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
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.
von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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.
0 0
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 Pluspunkte 0 Minuspunkte
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
von uafjv uafjv Tutor(in) (168k Punkte)  
...