Mecanismo de acceso al oráculo Ruzzo-Simon-Tompa

$\mathsf{NL} \nsubseteq \mathsf{P}$

Consideremos ahora las familias de circuitos con puertas de Oracle - por ejemplo, , donde es una clase de la complejidad del circuito que contiene logspace con acceso a Oracle a otra clase , a través de puertas de Oracle adjuntas a la base de . ¿Hay algún ejemplo patológico similar en espíritu al artículo de Ladner-Lynch, conocido por tales clases? ¿Cuál sería una restricción similar a RST necesaria para tales clases? En caso de que haya tales ejemplos, ¿estoy en lo cierto al adivinar que un análogo RST sería insistir en que sea una familia de circuitos con espacio de registro uniforme? $A^B$ $A$ $B$ $A$ $A$

cc.complexity-theory complexity-classes circuit-complexity oracles relativization Nikhil
fuente

Respuestas:

En este artículo se puede encontrar una definición de acceso al oráculo que funciona para las clases de complejidad de circuitos pequeños (las jerarquías y ), así como para las clases espaciales logarítmicas, con la propiedad de que todas las inclusiones conocidas se relativizan. $AC^k$ $NC^k$

Klaus Aehlig, Stephen Cook y Phuong Nguyen: Relativizing Small Complexity Classes and its Theories, CSL 2007, Springer LNCS 4646

Jan Johannsen
fuente

Gracias por la anotación. Pero todavía no tengo una idea clara de cómo RST se aplica a los circuitos con puertas de oráculo. Espero que no le importe si espero un momento para ver si hay otras opiniones interesantes sobre este tema, antes de aceptar su respuesta.

Nikhil