Wie sehen Komplexitätsklassen aus, wenn wir Turing-Reduktionen verwenden?

Um über Dinge wie die NP-Vollständigkeit nachzudenken, verwenden wir normalerweise Mehrfachreduktionen (dh Karp-Reduktionen). Dies führt zu Bildern wie diesen:

(unter Standardvermutungen). Ich bin sicher, wir sind alle mit solchen Dingen vertraut.

Welches Bild bekommen wir, wenn wir mit Turing-Reduktionen (dh Cook-Reduktionen) arbeiten? Wie verändert sich das Bild?

Was sind insbesondere die wichtigsten Komplexitätsklassen und in welcher Beziehung stehen sie zueinander? Ich vermute, dass die Rolle spielt, die früher von und (weil unter Turing-Reduktionen genauso geschlossen ist wie unter Karp-Reduktionen); ist das ungefähr richtig? $P^{NP}$ $NP$ $coNP$ $P^{NP}$ $NP$

Sollte das Bild also jetzt wie aussehen , dh wie folgt? $P \subset P^{NP} \subset PH \subset PSPACE$

Gibt es eine neue Sequenz, die eine Rolle spielt, die der Polynomhierarchie entspricht? Gibt es eine natürliche Folge von Komplexitätsklassen , ,, ..., so dass jede Komplexitätsklasse unter Turing-Reduktionen geschlossen wird? Was ist die "Grenze" dieser Sequenz: es ? Wird erwartet, dass sich jede Klasse in der Sequenz von der vorherigen unterscheidet? (Mit "erwartet" meine ich unter plausiblen Vermutungen, ähnlich dem Sinne, in dem erwartet wird, dass .) $C_0=P$ $C_1=P^{NP}$ $C_2=?$ $PH$ $P \ne NP$

Verwandte: Viele-Eins-Reduktionen vs. Turing-Reduktionen, um NPC zu definieren . In diesem Artikel wird erklärt, dass wir mit Karp-Reduktionen arbeiten, weil wir dadurch eine feinkörnigere, reichhaltigere und präzisere Hierarchie erhalten. Im Wesentlichen frage ich mich, wie die Hierarchie aussehen würde, wenn wir mit Turing-Reduktionen arbeiten würden: Wie die gröbere, weniger reiche, weniger präzise Hierarchie aussehen würde.

Möglicherweise sind einige Informationen auf mehrere Fragen verteilt .

Raphael

Aus dieser Frage zB Antwort: "Es wird vermutet, dass es sich um unterschiedliche Begriffe handelt. Die Unterscheidung zwischen coNP und NP verschwindet mit Turing-Reduktionen." Beachten Sie auch, dass coNP ≠ NP (weit verbreitet) P ≠ NP impliziert (P ist unter Komplement geschlossen). Es ist also mit einigen tief offenen Fragen der Komplexitätstheorie verbunden.

vzn

Danke, @Raphael, ich habe all diese Punkte überprüft und glaube nicht, dass sie meine Fragen beantworten.

Sie können . Einige Autoren bezeichnen sie mit (ähnlich den und ). Es ist im Wesentlichen der Turing-Abschluss der Polynomhierarchie. Wir haben Daher . $\mathsf{P}^{\Sigma^\mathsf{P}_i}$ $\square^\mathsf{P}_i$ $\Delta^\mathsf{P}_i$ $\nabla^\mathsf{P}_i$

P^{Σ_{i}^{P}} \subseteq {N P}^{Σ_{i}^{P}} = Σ_{i + 1}^{P} \subseteq P^{Σ_{i + 1}^{P}}

$\mathsf{P}^{\Sigma^\mathsf{P}_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}_i}= \Sigma^\mathsf{P}_{i+1}\subseteq \mathsf{P}^{\Sigma^\mathsf{P}_{i+1}}$

P^{P H} = \sum_{i \geq 0} P^{Σ_{i}^{P}} = \sum_{i \geq 0} Σ_{i}^{P} = P H

$\mathsf{P^{PH}} = \sum_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}_i} = \sum_{i\geq 0}\Sigma^\mathsf{P}_{i} = \mathsf{PH}$

Wenn die Polynomhierarchie nicht zusammenbricht, sind alle Einschlüsse streng.

Kaveh
quelle

Wie sehen Komplexitätsklassen aus, wenn wir Turing-Reduktionen verwenden?

Antworten: