Polynomialzeithierarchie (PH)
2007-09-25 20:12
NaZo
Ich habe eine Verständnisfrage zur Komplexitätsklasse PH, der Polynomialzeithierarchie.
Laut AUK-Skript (SS 07), Seite 273 wird diese folgendermaßen definiert:
[latex]\Sigma_1 = \mathcal{NP}[/latex]
[latex]\Sigma_{k+1} = \mathcal{NP}^{\Sigma_k}[/latex]
[latex]\mathcal{PH} = \bigcup_{k=1}^\infty\Sigma_k[/latex]
Dabei steht [latex]\mathcal{NP}^{\Sigma_k}[/latex] nach meinem Verständnis für die Menge der Sprachen, die durch eine nichtdeterministische Turingmaschine in polynomieller Zeit akzeptiert werden, und zwar mit Hilfe eines Orakels, welches eine Sprache aus [latex]\Sigma_k[/latex] akzeptiert.
Es sei offen, ob folgende Inklusionen echt sind, oder nicht:
[latex]\mathcal{NP} \subseteq \Sigma_1 \subseteq \Sigma_2 \subseteq … \subseteq \mathcal{PH}[/latex]
Und hier fängt mein Problem an:
Nehmen wir mal als Beispiel [latex]\Sigma_2 = \mathcal{NP}^{\Sigma_1} = \mathcal{NP}^\mathcal{NP}[/latex].
Für ein Problem [latex]S_2 \in \Sigma_2[/latex] bedeutet dies also, wenn ich es richtig verstehe, dass es eine nichtdeterministische Turingmaschine A gibt, die [latex]S_2[/latex] in polynomieller Zeit löst, und dabei ein Orakel befragt, das ein Problem [latex]S_1 \in \mathcal{NP}[/latex] löst.
"In polynomieller Zeit lösen" bedeutet, dass A maximal [latex]O(n^k), k \geq 1[/latex] Schritte zur Lösung benötigt. Das wiederum bedeutet aber ja auch, dass sie maximal [latex]O(n^k)[/latex]-mal das Orakel befragen kann.
Statt eines Orakels, das [latex]S_1[/latex] in einem Schritt löst, zu verwenden, kann ich doch aber auch eine andere NTM B befragen, die [latex]S_1[/latex] in maximal [latex]O(n^r), r \geq 1[/latex] Schritten löst, denn [latex]S_1 \in \mathcal{NP}[/latex]. Auch kann ich mir dann eine NTM A' vorstellen, die wie A ist, außer dass B da schon geschickt eingebaut ist.
Wenn jetzt also A mit Orakel maximal [latex]O(n^k)[/latex] Schritte braucht, und B maximal [latex]O(n^r)[/latex], dann braucht doch A' maximal [latex]O(n^k) O(n^r) = O(n^k n^r) = O(n^{k+r})[/latex] Schritte.
Daraus würde dann folgen, dass [latex]S_2 \in \mathcal{NP}[/latex] und da [latex]S_2[/latex] beliebig aus [latex]\Sigma_2[/latex] ist, [latex]\Sigma_2 \subseteq \mathcal{NP}[/latex] und damit [latex]\Sigma_2 = \mathcal{NP}[/latex].
Das ganze könnte man dann natürlich per vollständiger Induktion auch für [latex]\Sigma_k, k > 2[/latex] zeigen, also gelte dann auch [latex]\mathcal{PH} = \mathcal{NP}[/latex].
So, das ganze sieht für mich erstmal so aus, als hätte ich das Problem gelöst. Viel wahrscheinlicher finde ich aber natürlich, dass ich irgendwo einen Denkfehler habe. Kann mir da bitte jemand helfen?
Allerdings macht das Ergebnis in meinen Augen auch Sinn, weil ich den Nutzen dieser [latex]\mathcal{NP}^\mathcal{NP}[/latex] Konstruktion sowieso nicht ganz verstehe. Wenn das Orakel, dass ich befrage, nicht mächtiger ist, als ich selbst, kann ich mein Problem doch gleich allein lösen.
Deshalb muss ja auch ein Problem, dass ich auf ein NP-Problem reduzieren möchte, in [latex]\mathcal{P}^\mathcal{NP}[/latex] sein, und eins, dass ich auf ein P-Problem reduzieren möchte, in [latex]\mathcal{L}^\mathcal{P}[/latex] usw…
Edit: Schönheitskorrekturen
Laut AUK-Skript (SS 07), Seite 273 wird diese folgendermaßen definiert:
[latex]\Sigma_1 = \mathcal{NP}[/latex]
[latex]\Sigma_{k+1} = \mathcal{NP}^{\Sigma_k}[/latex]
[latex]\mathcal{PH} = \bigcup_{k=1}^\infty\Sigma_k[/latex]
Dabei steht [latex]\mathcal{NP}^{\Sigma_k}[/latex] nach meinem Verständnis für die Menge der Sprachen, die durch eine nichtdeterministische Turingmaschine in polynomieller Zeit akzeptiert werden, und zwar mit Hilfe eines Orakels, welches eine Sprache aus [latex]\Sigma_k[/latex] akzeptiert.
Es sei offen, ob folgende Inklusionen echt sind, oder nicht:
[latex]\mathcal{NP} \subseteq \Sigma_1 \subseteq \Sigma_2 \subseteq … \subseteq \mathcal{PH}[/latex]
Und hier fängt mein Problem an:
Nehmen wir mal als Beispiel [latex]\Sigma_2 = \mathcal{NP}^{\Sigma_1} = \mathcal{NP}^\mathcal{NP}[/latex].
Für ein Problem [latex]S_2 \in \Sigma_2[/latex] bedeutet dies also, wenn ich es richtig verstehe, dass es eine nichtdeterministische Turingmaschine A gibt, die [latex]S_2[/latex] in polynomieller Zeit löst, und dabei ein Orakel befragt, das ein Problem [latex]S_1 \in \mathcal{NP}[/latex] löst.
"In polynomieller Zeit lösen" bedeutet, dass A maximal [latex]O(n^k), k \geq 1[/latex] Schritte zur Lösung benötigt. Das wiederum bedeutet aber ja auch, dass sie maximal [latex]O(n^k)[/latex]-mal das Orakel befragen kann.
Statt eines Orakels, das [latex]S_1[/latex] in einem Schritt löst, zu verwenden, kann ich doch aber auch eine andere NTM B befragen, die [latex]S_1[/latex] in maximal [latex]O(n^r), r \geq 1[/latex] Schritten löst, denn [latex]S_1 \in \mathcal{NP}[/latex]. Auch kann ich mir dann eine NTM A' vorstellen, die wie A ist, außer dass B da schon geschickt eingebaut ist.
Wenn jetzt also A mit Orakel maximal [latex]O(n^k)[/latex] Schritte braucht, und B maximal [latex]O(n^r)[/latex], dann braucht doch A' maximal [latex]O(n^k) O(n^r) = O(n^k n^r) = O(n^{k+r})[/latex] Schritte.
Daraus würde dann folgen, dass [latex]S_2 \in \mathcal{NP}[/latex] und da [latex]S_2[/latex] beliebig aus [latex]\Sigma_2[/latex] ist, [latex]\Sigma_2 \subseteq \mathcal{NP}[/latex] und damit [latex]\Sigma_2 = \mathcal{NP}[/latex].
Das ganze könnte man dann natürlich per vollständiger Induktion auch für [latex]\Sigma_k, k > 2[/latex] zeigen, also gelte dann auch [latex]\mathcal{PH} = \mathcal{NP}[/latex].
So, das ganze sieht für mich erstmal so aus, als hätte ich das Problem gelöst. Viel wahrscheinlicher finde ich aber natürlich, dass ich irgendwo einen Denkfehler habe. Kann mir da bitte jemand helfen?
Allerdings macht das Ergebnis in meinen Augen auch Sinn, weil ich den Nutzen dieser [latex]\mathcal{NP}^\mathcal{NP}[/latex] Konstruktion sowieso nicht ganz verstehe. Wenn das Orakel, dass ich befrage, nicht mächtiger ist, als ich selbst, kann ich mein Problem doch gleich allein lösen.
Deshalb muss ja auch ein Problem, dass ich auf ein NP-Problem reduzieren möchte, in [latex]\mathcal{P}^\mathcal{NP}[/latex] sein, und eins, dass ich auf ein P-Problem reduzieren möchte, in [latex]\mathcal{L}^\mathcal{P}[/latex] usw…
Edit: Schönheitskorrekturen