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

Beantwortet: b): könnten in "L1/L2)" auch NP-vollständige Probleme genannt werden?

Fri, 25 Sep 2015 13:17:16 +0000

Hallo,

nein, das stimmt so nicht.

Solange \(P \neq NP\) gilt, stimmt aber zumindest die eine Richtung: Wenn wir davon ausgehen, dass \( NP\)-vollständige Probleme nicht mit (det.) Zeitbedarf \( O(n^3) \) gelöst werden können, was ja die Komplexität des Wortproblems für Typ-2-Sprachen ist, dann gilt auf jeden Fall für jedes \( NP\)-vollständige Problem \( X: X \notin L_2\).

Umgekehrt gibt es zwar \( NP\)-vollständige Probleme wie \(SAT\), die auf linearem Platz, also in \( DSPACE(n)\) berechnet werden können (was ja der Definition von \( L_1\) auf Automatenebene entspricht), aber es gibt auch \( NP\)-vollständige Probleme, für die das nicht gilt. Solche Probleme sind dann nicht in \( L_1\), also auch nicht in \(L_1 \backslash L_2\).

Sie könnten also \(SAT\) angeben und vermutlich noch weitere ähnliche Probleme, aber jedenfalls nicht pauschal alle \(NP\)-vollständigen.

Das war trotzdem keine schlechte Frage! Ich weiß nicht, warum sie so lange unbeantwortet blieb.

Viele Grüße

Lukas König

Beantwortet: Wäre die Diagonalsprache auch ein korrektes Beispiel für die Antwort im b Teil der Aufgabe?

Fri, 25 Sep 2015 13:12:00 +0000

Hallo,

bitte verwechseln Sie die Komplexitätsklasse \( P\) nicht mit der Menge aller Sprachen \( p(E^\star)\)! Letzteres ist im klassischen Sinn keine Komplexitätsklasse, bzw. ist diese Bezeichnung nicht besonders sinnvoll, da darin alle Sprachen bzw. Probleme enthalten sind, unabhängig von Komplexität oder Berechenbarkeit. Wenn Ihnen solche Unterschiede nicht klar sind, sollten Sie sich das dringend nochmal anschauen!

Die Antwort auf Ihre Frage ist aber ja, denn \( L_{NA} \) ist die Diagonalsprache :-)

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

Beantwortet: Welche Komplexität hat das Halteproblem?

Fri, 25 Sep 2015 13:09:15 +0000

Das Halteproblem ist ist NP-schwer, aber nicht NP-vollständig. Wenn letzteres der Fall wäre, dann wäre das Halteproblem entscheidbar...

Tobias (Tutor)

Beantwortet: Wieso ist L nicht entscheidbar?

Fri, 25 Sep 2015 13:08:05 +0000

Semientscheidbar heißt, dass es einen Algorithmus/ein TM gibt, der irgendwann (in endlicher Zeit) terminiert, wennn die Antwort "JA" ist. Wenn die Antwort "Nein" ist, dann muss der Algorithmus/die TM nicht terminieren (siehe dazu auch das Erfüllbarkeitsproblem der Prädikatenlogik in Info I). Nichtentscheidbaren Probleme sind alle anderen Probleme, die nicht semi-entscheidbar sind. Entschiedbar ist ein Problem, wenn es einen Algorithmus gibt, der immer mit der richtigen Antwort nach endlicher Zeit terminiert.

Welches L meinst du/welchen Aufgabenteil? Kannst du zusätzlich bitte durch Schreibweise zwischen nichtentscheidbar (d.h. auch nicht semi-entscheidbar und nicht entscheidbar (Problem nicht in der Menge der entscheidbaren Probleme) unterscheiden? Sonst kann ich nicht eindeutig erkennen, was du meinst.

Tobias (Tutor)

Beantwortet: was ist LNA für eine Sprachklasse?

Fri, 25 Sep 2015 13:06:47 +0000

Hallo,

das steht eigentlich auf der VL Folie 5-24: Dort wird gezeigt, dass es keine TM gibt, die LNA akzeptiert, LNA also nicht in L0 liegt. Damit liegt LNA in der Potenzmenge ohne L0.

Viele Grüße,

Vivian (Tutor)

P.S.:

Falls du also mit Sprachklassen Typ 0-3 Sprachen meinst, dann kann man LNA keiner dieser Klassen zuordnen. P(E*)\L0 ist aber selbst auch eine Klasse, wie in der Musterlösung angegeben :)