Clases de complejidad donde

Una posible motivación para estudiar las clases de complejidad computacional es comprender el poder de los diferentes tipos de recursos computacionales (aleatoriedad, no determinismo, efectos cuánticos, etc.). Si lo miramos desde esta perspectiva, parece que podemos obtener un axioma plausible para cualquier intento de caracterizar qué cálculos son factibles en algún modelo:

• Cualquier cálculo factible siempre puede invocar otro cálculo factible como una subrutina. En otras palabras, suponga que los programas se consideran factibles de ejecutar. Luego, si construimos un nuevo programa conectando P y Q , de modo que P realice llamadas de subrutina a Q , entonces este nuevo programa también es factible.$P,Q$$P$$Q$$P$$Q$

Traducido al lenguaje de las clases de complejidad, este axioma equivale al siguiente requisito:

• Si es una clase de complejidad intención de captura que los cálculos son factibles en algún modelo, entonces debemos tener C C = C .$C$$C^C = C$

(Aquí representa los cómputos en C que pueden invocar un oráculo de C ;. Que es una clase de complejidad oráculo) Por lo tanto, vamos a llamar a una clase de complejidad C plausibles si satisface C C = C .$C^C$$C$$C$$C$ $C^C=C$

Mi pregunta: ¿Qué clases de complejidad conocemos que sean plausibles (según esta definición de plausible)?

Por ejemplo, es plausible, ya que P P = P . ¿Tenemos B P P B P P = B P P ? ¿Qué pasa con B Q P B Q P = B Q P ? ¿Cuáles son algunas otras clases de complejidad que cumplen con este criterio?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Sospecho que (o al menos, esa sería nuestra mejor suposición, incluso si no podemos demostrarlo). ¿Existe una clase de complejidad que capture el cálculo no determinista y que sea plausible, según esta definición? Si dejamos que C denote la clase de complejidad más pequeña tal que N P ⊆ C y C C ⊆ C , ¿hay alguna caracterización clara de esta C ?$NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

ha sido probado enFortalezas y Debilidades de la Computación CuánticaBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

Según el zoo complejidad, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Aquí hay algunas respuestas a algunas de las preguntas, pero ciertamente no todas:

Aparentemente, de acuerdo con Wikipedia , tenemos , B P P B P P = B P P , P S P A C E P S P A C E = P S P A C E , L L = L , y ⊕ P ⊕ P = ⊕ P . Ver también Qué es la clase de complejidad ⊕ P$P^P=P$$BPP^{BPP}=BPP$$PSPACE^{PSPACE}=PSPACE$$L^L=L$$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$ , que observa que.$\oplus P^{\oplus P} = \oplus P$

Además, si , entonces C se cierra bajo el complemento. Por lo tanto, es poco probable que N P N P = N P : esto implicaría que N P = co- N P , lo que parece poco probable. Parece que la clase de complejidad plausible más pequeña que contiene N P es P H (ver Wikipedia ).$C^C=C$$C$$NP^{NP}=NP$$NP=\textit{co-}NP$$NP$$PH$

No sé cuál es la situación con . No sé si hay otros ejemplos interesantes de clases de complejidad plausible.$BQP$

Una clase de complejidad se llama auto-baja precisamente cuando C C = C . En general, la "bajeza" se estudió mucho en los años 80 y 90: Google descubrirá mucho para usted.$C$$C^C = C$

Este comentario enumera L (espacio de registro), NC (profundidad de polylog), P, BPP, BQP y PSPACE como ejemplos de clases de baja complejidad propia.