À quoi ressemblent les classes de complexité, si nous utilisons des réductions de Turing?

Pour raisonner sur des choses comme l'exhaustivité de NP, nous utilisons généralement plusieurs réductions (c.-à-d. Des réductions de Karp). Cela conduit à des images comme celle-ci:

(sous conjectures standard). Je suis sûr que nous connaissons tous ce genre de choses.

Quelle image obtenons-nous si nous travaillons avec des réductions Turing (c.-à-d. Des réductions Cook)? Comment l'image change-t-elle?

En particulier, quelles sont les classes de complexité les plus importantes et comment sont-elles liées? Je suppose que joue le rôle qui était auparavant occupé par et (parce que est fermé sous les réductions de Turing de la même manière que est fermé sous les réductions de Karp); c'est à peu près ça? $P^{NP}$ $NP$ $coNP$ $P^{NP}$ $NP$

Donc, l'image devrait-elle ressembler à maintenant, c'est-à-dire quelque chose comme ce qui suit? $P \subset P^{NP} \subset PH \subset PSPACE$

Y a-t-il une nouvelle séquence qui joue un rôle qui correspond à la hiérarchie polynomiale? Existe-t-il une séquence naturelle de classes de complexité , ,, ..., de sorte que chaque classe de complexité soit fermée sous Réductions de Turing? Quelle est la "limite" de cette séquence: est-ce ? Est-il prévu que chaque classe de la séquence soit différente de la précédente? (Par "attendu", je veux dire sous des conjectures plausibles, similaires au sens dans lequel on s'attend à ce que .) $C_0=P$ $C_1=P^{NP}$ $C_2=?$ $PH$ $P \ne NP$

Connexes: plusieurs réductions par rapport aux réductions de Turing pour définir le PNJ . Cet article explique que la raison pour laquelle nous travaillons avec les réductions de Karp est qu'il nous donne une hiérarchie plus fine, plus riche et plus précise. Essentiellement, je me demande à quoi ressemblerait la hiérarchie si nous travaillions avec des réductions de Turing: à quoi ressemblerait la hiérarchie plus grossière, moins riche et moins précise.

Nous pouvons avoir des informations réparties sur plusieurs questions .

Raphael

à partir de cette question, par exemple, répondre "ils sont supposés être des notions distinctes. la distinction de coNP vs NP disparaît avec les réductions de Turing." noter également que coNP ≠ NP (largement conjecturé) implique P ≠ NP (P est fermé sous complément). donc c'est lié à des questions de théorie de la complexité ouverte.

vzn

Merci, @Raphael, j'ai passé en revue tout cela, et je ne pense pas qu'ils répondent à aucune de mes questions.

Vous pouvez utiliser . Certains auteurs les désignent par des notations (similaires aux notations et ). C'est essentiellement la fermeture de Turing de la hiérarchie polynomiale. Nous avons Par conséquent . $\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}$

Si la hiérarchie polynomiale ne s'effondre pas, toutes les inclusions sont strictes.

Kaveh
la source

À quoi ressemblent les classes de complexité, si nous utilisons des réductions de Turing?

Réponses: