Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2012-H-05

Beantwortet: Warum ist F nicht in p(E*)?

Sun, 12 Feb 2017 22:02:33 +0000

Hallo,

da B in NP liegt und gilt: B <pol F muss F laut Definition in NP-schwer liegen.

Im Hinweis der Aufgabe ist auch nochmal aufgeführt, dass du hier nur zw. NP-vollständig und nicht-NP-vollständig unterscheiden musst.

Grüße

Beantwortet: Wenn man die B=NP erst betrachtet:

Sat, 13 Feb 2016 10:50:00 +0000

Nein, kein direkter Denkfehler, aber nicht konsequent zu Ende gedacht: CLIQUE, A und B liegen selbstverständlich in NP. Aber wir können diese Zugehöigkeit zu NP eben noch konkretisieren, da wir wissen, dass CLIQUE als NP-vollständiges Problem (und damit zu den schwersten Problemen in NP gehörendes Problem) auf A und B reduzierbar ist. Damit gehören A und B eben auch nicht einfach nur zu den NP-Problemen, sondern zu den schwersten in NP (also NP-vollständig).

Ich hoffe, das hilft weiter!

VG,
Janine (Tutorin)

Beantwortet: Warum liegen A und B in NP vollständig?

Thu, 11 Feb 2016 21:30:07 +0000

Hallo uxduy!

Um A und B richtig einsortieren zu können, genügt es nicht, nur die erste Zeile zu betrachten, sondern auch die zweite Zeile ist hier zu beachten!

Aus der ersten Zeile folgt, dass CLIQUE polynamialzeit-reduzierbar auf A ist, A wiederum auf B und B wiederum auf F. Wir wissen (bzw. es ist in der Aufgabenstellung gegeben), dass CLIQUE selbst NP-vollständig ist. Wenn wir also CLIQUE in polynomieller Zeit zunächst auf A reduzieren können, dann muss A mindestens so schwierig oder schwieriger sein als CLIQUE. Das bedeutet, dass wir zunächst davon ausgehen, dass A NP-schwer ist, denn die Definition von NP-schweren Problemem ist ja gerade, dass sich alle Probleme aus NP (also auch die NP-vollständigen Probleme wie hier CLIQUE) darauf in polynomieller Zeit reduzieren lassen. Gleiches gilt für B und F (wegen der Transitivität der polynomiellen Reduzierbarkeit, siehe Tutorium 3 , Aufgabe 6). Damit gehen wir also bis jetzt davon aus, dass A, B und F alle drei in NP-schwer liegen.

So, und nun kommt aber die zweite gegebene Zeile der Aufgabenstellung hinzu: B ist Element von NP. Die Schnittmenge von NP-schwer und NP ist gerade NP-vollständig, also wissen wir jetzt, dass B in NP-vollständig liegt. Und da A in polynomieller Zeit auf B reduziert werden kann, kann A nicht schwerer sein als B, dh. auch A liegt in NP-vollständig.

Die Lage von F können wir nicht weiter eingrenzen, da es eben bildlich gesprochen "ganz rechts" in der Reduzierbarkeits-Kette steht und wir damit nur wissen, dass es mindestens so schwer ist wie NP-vollständig.

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)

Beantwortet: Aufgabe 5

Tue, 02 Feb 2016 17:33:31 +0000

Unsere einzige Information über F ist hier, dass CLIQUE polynomialzeitreduzierbar auf F ist. Da CLIQUE NP-vollständig ist, also unter anderem NP-schwer ist, können wir folgern, dass F ebenfalls NP-schwer ist also dass jedes Problem aus NP polynomialzeitreduzierbar auf F ist. Dies ist möglich, da wir wissen, dass bereits jedes Problem aus NP auf CLIQUE polynomialzeitreduzierbar ist. Über die Zugehörigkeit von F zu der Menge NP (bzw. einer anderen Menge) haben wir jedoch keine Information. Deshalb liegt es nur in NP-schwer.

Von D wissen wir nur, dass PRIMES polynomialzeitreduzierbar auf D ist. Das grenzt jedoch nicht weiter ein, in welcher Klasse das Problem liegt, weshalb es ganz außen eingeordnet ist.

C liegt in P, da es auf PRIMES polynomialzeitreduzierbar ist. Ensprechend muss es "mindestens so leicht wie PRIMES sein". Folglich wird es in die Klasse P eingeordnet

Grüße,
Lukas (Tutor)

Beantwortet: F in NP vollständig?

Fri, 25 Sep 2015 12:49:55 +0000

Hallo,

Sie wissen nur, dass F in NP-schwer liegt, nicht jedoch ob es auch in NP liegt (möglich ist das natürlich, aber nicht endeutig vorgegeben!) also kann F nur in NP-schwer (außerhalb von NP-vollst.) eingezeichnet werden.

Viele Grüße,

Janina (Tutorin)

Beantwortet: Warum ist D nicht in NP-schwer?

Fri, 25 Sep 2015 12:48:57 +0000

Hallo,

D muss in p(E*), weil in dieser Aufgabe gefordert ist, dass die Probleme so genau wie möglich geordnet werden müssen. Die einzige Angabe die bezüglich D gegeben ist, ist dass das Problem mindestens so schwer zu lösen ist wie PRIMES. Es ist allerdings keine obere Schranke bezüglich der Komplexität gegeben, deshalb kann keine Aussage getroffen werden, ob das Problem in NP, NP-schwer, entscheidbaren, seminentscheidbaren oder in p(E*) liegt. Deshalb müssen wir D in p(E*) einordnen.

Grundsätzlich ist die Polynomialzeitreduktion nicht auf die Bereiche P,NP oder NP-schwer beschränkt, sondern kann durch über alle Komplexitätsklassen ausgeführt werden.

Viele Grüße,

Sebastian(Tutor)

Beantwortet: F auch semi-entscheidbar?

Fri, 25 Sep 2015 12:43:53 +0000

Ich sehe keinen Grund, warum F semi-entscheidbar sein muss. Für meine Begriffe kannst du es irgendwo in NP-Schwer einzeichnen.

Tobias (Tutor)

Beantwortet: Wie muss "tief" beim Einordnen interpretiert werden?

Fri, 25 Sep 2015 12:42:53 +0000

Hallo,

"tiefstmöglich" bedeutet, dass du die "kleinste" Klasse angibst, in der das Problem 100%ig drinliegt. In deinem Beispiel heißt das:

D kann in P liegen, muss es aber nicht. Man kann ein Problem aus P beliebig verkomplizieren und demnach z.B. auf ein Problem aus NP, L0 usw. reduzieren. Deswegen kannst du hier keine sichere Aussage darüber treffen, wo konkret dein D liegt, also musst du dich hier mit der Potenzmenge begnügen. Genauso macht man es auch z.B. mit der 2. Information. Je nachdem wie B aussieht, könnte B auch in P liegen, was eine Teilmenge von NP ist. Aber das Problem ist, dass man dies anhand der gegebenen Daten nicht entscheiden kann. Die genaueste Aussage lautet also: B in NP.

Viele Grüße,

Vivian (Tutor)

Beantwortet: Beispiele zu den Komplexitätsklassen?

Fri, 25 Sep 2015 10:38:54 +0000

P: Wortproblem für Typ 3 / Typ 2 Sprachen, Sortieren, Automatenminimierung, uvm...

NP: Alles von P, alles aus NP-vollständig und weitere (nicht in Vorlesung)

NP - vollständig: SAT, Clique, uvm...

NP-schwer: Halteproblem, Clique, (3)-SAT, alles aus NP-vollständig

entscheidbar: Menge der Primzahlen, Palindrome, alle aus NP, uvm...

L0 (semientscheidbar): Alles aus P, alles aus entscheidbar, Halteproblem;
ACHTUNG: Diagonalsprache L_NA ist hier FALSCH

p(E*): Alles aus P,Diagonalsprache L_NA; das sind alle Probleme, die überhaupt definierbar sind.

> Und noch eine Frage zu der Aussage "Entscheidbare bzw. semientscheidbare Probleme, die nicht NP-schwer sind, kennen Sie viele. Da wären schonmal alle Probleme aus P". Wäre das auch so, wenn gelten würde NP = P, oder hat das keine Auswirkungen auf NP-schwer?

Das ist eine gute Frage, danke! Ich muss mich korrigieren und sagen: solche Probleme kennen Sie viele unter der Annahme P≠NP. Wenn P=NP, dann sind (fast) alle Probleme aus P auch NP-schwer.

Viele Grüße

Lukas König und Friederike Pfeiffer

Beantwortet: praktische (semi/nicht-) entscheidbare Probleme die nicht in NP-Schwer liegen?

Fri, 25 Sep 2015 10:37:20 +0000

Entscheidbare bzw. semientscheidbare Probleme, die nicht NP-schwer sind, kennen Sie viele. Da wären schonmal alle Probleme aus P, die natürlich auch praktische Relevanz haben. Unter den nicht entscheidbaren Problemen haben Sie die Diagonalsprache L_NA kennengelernt, die (meines Wissens) nicht NP-schwer ist.

Ich hoffe, das trägt zum Verständnis bei, sonst fragen Sie bitte einfach wieder.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: Warum ist E nicht in NP-schwer?

Fri, 25 Sep 2015 10:35:16 +0000

Hallo,

hier muss man vorsichtig sein!

Zunächst mal, ja, das Halteproblem ist NP-schwer. Wenn Sie es in den äußersten Bereich des NP-schwer-Kreises gemalt hätten, wäre das auch in Ordnung gewesen. Allerdings wird das nicht direkt in der Vorlesung thematisiert, weshalb wir es, um Verwirrung zu vermeiden, nur in den semientscheidbaren Bereich gemalt haben.

Wichtig ist aber richtigzustellen, dass sich "semientscheidbar" und "nicht entscheidbar" nicht ausschließen. Sowohl das allgemeine Halteproblem als auch das spezielle Halteproblem sind sowohl nicht entscheidbar als auch semientscheidbar. In der Vorlesung haben wir nur das allgemeine Halteproblem behandelt.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen