Classes de complexidade em que

Uma motivação possível para o estudo de classes de complexidade computacional é entender o poder de diferentes tipos de recursos computacionais (aleatoriedade, não determinismo, efeitos quânticos etc.). Se olharmos para essa perspectiva, parece que podemos obter um axioma plausível para qualquer tentativa de caracterizar quais computações são viáveis ​​em algum modelo:

• Qualquer cálculo viável sempre pode invocar outro cálculo viável como sub-rotina. Em outras palavras, suponha que os programas sejam considerados viáveis ​​de executar. Então, se construirmos um novo programa conectando P e Q , para que P faça chamadas de sub-rotina para Q , esse novo programa também será possível.$P,Q$$P$$Q$$P$$Q$

Traduzido para o idioma das classes de complexidade, esse axioma corresponde ao seguinte requisito:

• Se é uma classe de complexidade intenção de captura que os cálculos são viáveis em algum modelo, então devemos ter C C = C .$C$$C^C = C$

(Aqui representa cálculos em C que podem invocar um oráculo de C ;. Que é uma classe de complexidade Oracle) Então, vamos chamar uma classe de complexidade C plausível se satisfaz C C = C .$C^C$$C$$C$$C$ $C^C=C$

Minha pergunta: Que classes de complexidade sabemos, que são plausíveis (por essa definição de plausível)?

Por exemplo, é plausível, uma vez que P P = P . Temos B P P B P P = B P P ? E quanto a B Q P B Q P = B Q P ? Quais são algumas outras classes de complexidade que atendem a esse critério?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Suspeito que (ou pelo menos, esse seria o nosso melhor palpite, mesmo que não possamos provar isso). Existe uma classe de complexidade que captura a computação não determinística e que é plausível, sob esta definição? Se deixarmos C denotar a menor classe de complexidade, de modo que N P ⊆ C e C C ⊆ C , existe alguma caracterização limpa desse C ?$NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

foi provado emForças e Fraquezas da Quantum ComputingBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

De acordo com a complexidade do jardim zoológico, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Aqui estão algumas respostas para algumas das perguntas, mas certamente nem todas:

$P^P=P$$BPP^{BPP}=BPP$$PSPACE^{PSPACE}=PSPACE$$L^L=L$$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$$\oplus P^{\oplus P} = \oplus P$

$C^C=C$$C$$NP^{NP}=NP$$NP=\textit{co-}NP$$NP$$PH$

$BQP$

$C$$C^C = C$

Este comentário lista L (espaço de registro), NC (profundidade do polilog), P, BPP, BQP e PSPACE como exemplos de classes de baixa complexidade.