Como são as classes de complexidade, se usarmos as reduções de Turing?

Para raciocinar sobre coisas como NP-completeness, normalmente usamos muitas reduções de uma (por exemplo, reduções de Karp). Isso leva a imagens como esta:

(sob conjecturas padrão). Tenho certeza de que todos estamos familiarizados com esse tipo de coisa.

Que imagem temos, se trabalharmos com reduções de Turing (ou seja, reduções de Cook)? Como a imagem muda?

Em particular, quais são as classes de complexidade mais importantes e como elas se relacionam? Suponho que desempenhe o papel que costumava ser assumido por e (porque é fechado em reduções de Turing da mesma maneira que é fechado em reduções de Karp); isso é certo? $P^{NP}$ $NP$ $coNP$ $P^{NP}$ $NP$

Então, a imagem deve se parecer com agora, ou seja, algo como o seguinte? $P \subset P^{NP} \subset PH \subset PSPACE$

Existe alguma nova sequência que desempenhe um papel que corresponda à hierarquia polinomial? Existe uma sequência natural de classes de complexidade , ,, ..., de modo que cada classe de complexidade seja fechada em reduções de Turing? Qual é o "limite" dessa sequência: é ? É esperado que cada classe na sequência seja diferente da anterior? (Por "esperado", quero dizer sob conjecturas plausíveis, semelhante ao sentido em que é esperado que ) $C_0=P$ $C_1=P^{NP}$ $C_2=?$ $PH$ $P \ne NP$

Relacionado: Reduções de uma vez vs. Reduções de Turing para definir o NPC . Esse artigo explica que a razão pela qual trabalhamos com as reduções de Karp é que ela nos fornece uma hierarquia mais refinada, mais rica e mais precisa. Essencialmente, estou imaginando como seria a hierarquia se trabalhassemos com as reduções de Turing: como seria a hierarquia mais grosseira, menos rica e menos precisa.

Podemos ter algumas informações espalhadas por várias perguntas .

Raphael

a partir dessa pergunta, por exemplo, resposta "eles são conjecturados como noções distintas. a distinção de coNP vs NP desaparece com reduções de Turing". observe também que coNP ≠ NP (amplamente conjecturado) implica P ≠ NP (P é fechado sob complemento). por isso, está ligado a algumas questões profundas da teoria da complexidade aberta.

vzn

Obrigado, @Raphael, eu revi tudo isso e acho que eles não respondem a nenhuma das minhas perguntas.

Você pode usar . Alguns autores os denotam por (semelhante a e ). É essencialmente o fechamento de Turing da hierarquia polinomial. Temos Portanto, . $\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}$

Se a hierarquia polinomial não recolher, todas as inclusões serão estritas.

Kaveh
fonte

Como são as classes de complexidade, se usarmos as reduções de Turing?

Respostas: