Circuitos con oráculos versus máquinas de Turing con oráculos

13

En pocas palabras: ¿cuál es la correspondencia entre las máquinas de Turing con oráculos y las familias de circuitos uniformes con oráculos? ¿Cómo se definen estos últimos para obtener el mismo modelo computacional, para una máquina de Oracle Turing dada?

Esta puede ser una pregunta elemental, pero no es obvio dónde buscar, y soy el tipo de persona a la que le gusta asegurarse de que mis cimientos estén usando mortero de buena calidad. Si hay una referencia estándar, indíquemela. (El libro de Papadimitriou, por ejemplo, no parece describir circuitos con oráculos en absoluto).

Mi hipótesis de trabajo es esta: una familia de circuitos uniforme con acceso a un oráculo (por ejemplo, para resolver un problema de NP completo) se define de la siguiente manera:

  • Uno define una familia infinita de "puertas de oráculo" O n  , una para cada tamaño de circuito n, cada una de las cuales calcula una función f n  : {0,1} cn  → {0,1} para alguna constante c.

  • Las funciones f n calculadas por las puertas del oráculo O n deben ser "uniformes" en el siguiente sentido: para cualquier n <N y x  ∈ {0,1} n , requerimos f n ( x ) = f N (0 c ( N − n)  x  ) --- es decir, las puertas del oráculo deben usar una "codificación" consistente y extensible de sus entradas.

  • Luego, se define una familia de circuitos uniforme, donde las puertas de oráculo se encuentran entre las operaciones permitidas para el circuito, restringiendo el circuito para el tamaño de entrada n para usar la puerta O n .

Me imagino que algunas de las opciones anteriores pueden arreglarse arbitrariamente sin perder ninguna generalidad. Lo que me interesa es una referencia para la correspondencia, o al menos una descripción de cómo modificar la descripción anterior para obtener la estándar.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
fuente
Como sé que trabajas en información cuántica, recomendaría la encuesta de John Watrous sobre la complejidad computacional cuántica, donde también habla sobre los oráculos en los circuitos cuánticos y la consulta del oráculo en superposición.
Robin Kothari
El artículo de Watrous también es una buena referencia. Pero resultó que lo que necesitaba en este caso era estar de alguna manera desilusionado de la idea de que cualquiera quisiera definir una familia de circuitos relativizados de una manera que no se correspondiera con solo probar el mismo predicado para diferentes longitudes de cadena finita, al ser recordó que la semántica de un oráculo es clásicamente indicar pertenencia a algún conjunto Al final resultó que, dibujos de puertas de circuito con los símbolos "∈A?" en ellos era todo lo que necesitaba.
Niel de Beaudrap

Respuestas:

19

La mejor referencia para circuitos relativizados es el artículo de Chris Wilson "Relativized NC" http://www.springerlink.com/content/u727654246wu8662/

La segunda condición que tiene (cierre hacia abajo de O_n) no es necesaria para obtener la equivalencia entre P ^ O y los circuitos uniformes de polietileno con Oracle O. Además, su tercera condición debe desecharse, el tamaño del circuito impedirá el acceso a O_m para m más grande que el tamaño del circuito.

Lance Fortnow
fuente
No hay comentarios explícitos en el artículo de Wilson sobre las puertas del oráculo en sí; Pero en retrospectiva, si se toma el oráculo en serio como representante de la pertenencia a un conjunto de cadenas booleanas como con TM, entonces mi segunda condición es simplemente un problema (es decir, no hace falta decirlo). Por su observación de lo superfluo de mi tercera condición, es suficiente tener una familia infinita de puertas que deciden la membresía en A para cualquier tamaño de cadena finita en particular. Funciona para mi; Ojalá lo hubiera pensado antes.
Niel de Beaudrap
3
Comentarios para el beneficio de los espectadores casuales --- El artículo de Wilson define la contribución profunda de una puerta de oráculo en k bits para ser ceil (log k), en aparente analogía con el trabajo previo de Cook ("Una taxonomía de problemas con algoritmos paralelos rápidos" , Inform. Y Control, 64). Existe un problema técnico sobre si se deben permitir consultas de oráculo en el proceso de construcción de los circuitos mismos (cada uno de los cuales también puede usar oráculos): comenta que no parece importar. Al final, sin embargo, no está satisfecho por la existencia de A para la cual NC_1 ^ A no está contenido en NSPACE ^ A (O (n ^ k)), para cualquier constante k.
Niel de Beaudrap