Es könnte eventuell nützlich sein, einen zentralen Thread mit Begriffen, welche verwendet werden, aber so bisher im Studium nicht vorkamen, zu haben. Ich habe auch selbst einige Begriffsfragen.
Begriffe - dom - Domain, der Definitionsbereich einer Funktion - Rekursive Menge - Entscheidbare Menge, Rekursiv aufzählbar (hier nicht vorgekommen) bedeutet semientscheidbar - P^EXP, NP^EXP - Komplexitätsklassen von Sprachen, dessen Maschinen auf Orakel zurückgreifen können. Def.: Eine Sprache ist in P^A, wenn eine deterministische Polynomialzeit-TM M mit Zugriff zu einem Orakel für das Problem A gibt, welches überprüfen kann, ob ein Wort in A ist. Hier also die Klassen mit einem Orakel, welches in O(1) feststellen kann, ob ein Paar (M, w) in EXP ist. - Relativization barrier, relativizing - Wenn wir eine Analyse einer Sprache über eine Sprachklasse mit Orakel, etwa P^A oder P^B führen, so wird diese Analyse relativ zu der Sprachklasse geführt. Ein Ergebnis dieser Relativisierung ist, dass sich zeigen lässt, dass es zwei Sprachen A, B gibt, sodass P^A != NP^A und P^B = NP^B. Die "Barriere" wird vom Beweis nicht überschritten, da dieses Ergebnis erhalten bleibt. - partiell, total berechenbare Funktion - Für partiell berechenbare Funktionen existiert für den definierten Wertebereich, welcher definiert ist, eine TM, welche diese Werte berechnen kann. Bei total berechenbaren Funktionen ist der gesamte Wertebereich berechenbar, also die induzierte Sprache entscheidbar. Bei partiellen Funktionen ist die induzierte Sprache semientscheidbar. - Satz von Rice - Zu entscheiden, ob die Sprache L(M) einer Turing-Maschine M eine Eigenschaft hat (Regulär, Kontextfrei, ...), ist nicht entscheidbar. - Nichttriviale Eigenschaft: Eigenschaft von berechenbaren, als auch nicht berechenbaren Sprachen.
Noch nicht erklärte Begriffe
Beispiel für die Orakeldefinition: Nutze ein Orakel für das SAT-Problem. So lässt sich jedes NP-Problem polynomiell zu SAT reduzieren und mit dem Orakel lösen.
Beispiele für solche Sprachen wie im Satz von Rice sind - das Halteproblem H - REGULAR_TM: Liefert die TM M eine reguläre Sprache? L(M) regulär? - E_TM: Liefert die TM M die leere Sprache? L(M)={}? Mehr im Buch von Introduction To The Theory of Computation - M. Sipser, S. ~219
Ich würde diesen Kommentar nach Erklärungen dann aktualisieren.
Relativization barrier: Es wurde von Baker, Gill und Solovay gezeigt, dass für das P =? NP Problem kein relativizierender Beweis verwendet werden kann. Solche Beweise sind z.B. Diagonalisierung wie bei den Hierachietheoremen. Dazu wurden zwei Mengen A und B gefunden mit P^A = NP^A und P^B != NP^B Ein Problem ist in P^A, wenn es eine Turing Maschine mit Laufzeit in P gibt, die auf ein Orakel zugreifen kann, dass überprüft, ob ein Wort in A ist. D. h. ein Problem ist in P^A wenn es dafür einen polynomiellen Algorithmus gibr unter der hypothetischen Voraussetzung, dass mit der Laufzeit O(1) getestet werden kann, ob ein Wort in A ist. Mit P^EXP ist gemeint P^A, wobei A eine beliebige Menge ist, die EXP-vollständig ist.
Eine partiell berechenbare Funktion ist eine Funktion, die für die Werte berechenbar ist, für die sie definiert ist, also eine semiberechenbare Funktion. Eine total berechenbare Funktion ist zusätzlich überall definiert. Damit ist total berechenbar gleichbedeutend mit berechenbar.
Beim Satz von Rice ist eine Eigenschaft nicht trivial, wenn es sowohl durch TMs erkennbare Sprachen gibt, für die die Eigenschaft gilt, als auch durch TMs erkennbare Sprachen, für die diese Eigenschaft nicht gilt.
Ein Orakel ist ein hypothetiches Unterprogramm, das ein bestimmtes Problem, z.B. SAT, ohne Zeitaufwand lösen kann. Ein Problem A ist in der Klasse P^SAT, wenn man ein Programm mit polynomineller Laufzeit Schreiben kann, was das Orakel zum Lösen von SAT benutzt. Man spricht dann auch von polynom. Turing-Reduzierbarkeit.In LaTeX: A \le^p_T SAT.
Satz von Rice
Für eine Turing Maschine M ist eine Eigenschaft der Sprache L(M) nicht entscheidbar, wenn sie nicht trivial ist. Eine Eigenschaft ist nicht trivial, wenn es TMs gibt, deren Sprache die Eigenschaft haben UND TMs, deren Sprache die Eigenschaft nicht haben. Bei den in Valentins Kommentar genannten Beispielen ist das der Fall. In meinem Beweis habe ich in Lemma 2 eine nichtleere endliche Menge von Eingaben W. Da W endlich, kann ich für jede Teilmenge X von W eine TM M angeben mit { x in W | x in L(M)} = X. Diese Eigenschaft ist nicht trivial, wenn W nicht leer.
Günther Rothe, zuletzt aktualisiert am 14.01.2021
Lesedauer: 1 Minute(n)
4 Kommentare
Valentin Pickel sagt:
16.02.2021Es könnte eventuell nützlich sein, einen zentralen Thread mit Begriffen, welche verwendet werden, aber so bisher im Studium nicht vorkamen, zu haben. Ich habe auch selbst einige Begriffsfragen.
Begriffe
- dom - Domain, der Definitionsbereich einer Funktion
- Rekursive Menge - Entscheidbare Menge, Rekursiv aufzählbar (hier nicht vorgekommen) bedeutet semientscheidbar
- P^EXP, NP^EXP - Komplexitätsklassen von Sprachen, dessen Maschinen auf Orakel zurückgreifen können.
Def.: Eine Sprache ist in P^A, wenn eine deterministische Polynomialzeit-TM M mit Zugriff zu einem Orakel für das Problem A gibt, welches überprüfen kann, ob ein Wort in A ist.
Hier also die Klassen mit einem Orakel, welches in O(1) feststellen kann, ob ein Paar (M, w) in EXP ist.
- Relativization barrier, relativizing - Wenn wir eine Analyse einer Sprache über eine Sprachklasse mit Orakel, etwa P^A oder P^B führen, so wird diese Analyse relativ zu der Sprachklasse geführt. Ein Ergebnis dieser Relativisierung ist, dass sich zeigen lässt, dass es zwei Sprachen A, B gibt, sodass P^A != NP^A und P^B = NP^B. Die "Barriere" wird vom Beweis nicht überschritten, da dieses Ergebnis erhalten bleibt.
- partiell, total berechenbare Funktion - Für partiell berechenbare Funktionen existiert für den definierten Wertebereich, welcher definiert ist, eine TM, welche diese Werte berechnen kann. Bei total berechenbaren Funktionen ist der gesamte Wertebereich berechenbar, also die induzierte Sprache entscheidbar. Bei partiellen Funktionen ist die induzierte Sprache semientscheidbar.
- Satz von Rice - Zu entscheiden, ob die Sprache L(M) einer Turing-Maschine M eine Eigenschaft hat (Regulär, Kontextfrei, ...), ist nicht entscheidbar.
- Nichttriviale Eigenschaft: Eigenschaft von berechenbaren, als auch nicht berechenbaren Sprachen.
Noch nicht erklärte Begriffe
Beispiel für die Orakeldefinition: Nutze ein Orakel für das SAT-Problem. So lässt sich jedes NP-Problem polynomiell zu SAT reduzieren und mit dem Orakel lösen.
Beispiele für solche Sprachen wie im Satz von Rice sind
- das Halteproblem H
- REGULAR_TM: Liefert die TM M eine reguläre Sprache? L(M) regulär?
- E_TM: Liefert die TM M die leere Sprache? L(M)={}?
Mehr im Buch von Introduction To The Theory of Computation - M. Sipser, S. ~219
Ich würde diesen Kommentar nach Erklärungen dann aktualisieren.
Reiner Czerwinski sagt:
03.02.2021Relativization barrier: Es wurde von Baker, Gill und Solovay gezeigt, dass für das P =? NP Problem kein relativizierender
Beweis verwendet werden kann. Solche Beweise sind z.B. Diagonalisierung wie bei den Hierachietheoremen. Dazu wurden zwei
Mengen A und B gefunden mit P^A = NP^A und P^B != NP^B
Ein Problem ist in P^A, wenn es eine Turing Maschine mit Laufzeit in P gibt, die auf ein Orakel zugreifen kann, dass überprüft,
ob ein Wort in A ist. D. h. ein Problem ist in P^A wenn es dafür einen polynomiellen Algorithmus gibr unter der hypothetischen
Voraussetzung, dass mit der Laufzeit O(1) getestet werden kann, ob ein Wort in A ist.
Mit P^EXP ist gemeint P^A, wobei A eine beliebige Menge ist, die EXP-vollständig ist.
Eine partiell berechenbare Funktion ist eine Funktion, die für die Werte berechenbar ist, für die sie definiert ist, also eine semiberechenbare Funktion. Eine total berechenbare Funktion ist zusätzlich überall definiert. Damit ist total berechenbar gleichbedeutend
mit berechenbar.
Beim Satz von Rice ist eine Eigenschaft nicht trivial, wenn es sowohl durch TMs erkennbare Sprachen gibt, für die die Eigenschaft gilt, als auch durch TMs erkennbare Sprachen, für die diese Eigenschaft nicht gilt.
Valentin Pickel sagt:
16.02.2021Ich habe den Kommentar einmal aktualisiert.
Reiner Czerwinski sagt:
18.02.2021Orakel
Ein Orakel ist ein hypothetiches Unterprogramm, das ein bestimmtes Problem,
z.B. SAT, ohne Zeitaufwand lösen kann.
Ein Problem A ist in der Klasse P^SAT, wenn man ein Programm mit polynomineller
Laufzeit Schreiben kann, was das Orakel zum Lösen von SAT benutzt.
Man spricht dann auch von polynom. Turing-Reduzierbarkeit.In LaTeX: A \le^p_T SAT.
Satz von Rice
Für eine Turing Maschine M ist eine Eigenschaft der Sprache L(M) nicht
entscheidbar, wenn sie nicht trivial ist. Eine Eigenschaft ist nicht
trivial, wenn es TMs gibt, deren Sprache die Eigenschaft haben UND
TMs, deren Sprache die Eigenschaft nicht haben.
Bei den in Valentins Kommentar genannten Beispielen ist das der Fall.
In meinem Beweis habe ich in Lemma 2 eine nichtleere endliche Menge
von Eingaben W. Da W endlich, kann ich für jede Teilmenge X von W
eine TM M angeben mit { x in W | x in L(M)} = X. Diese Eigenschaft
ist nicht trivial, wenn W nicht leer.