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 pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur 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 cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
99 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)  
...