¿Es

23

En la encuesta "Circuitos cuánticos de pequeña profundidad" de D. Bera, F. Green y S. Homer (p. 36 de ACM SIGACT News, junio de 2007 vol. 38, no. 2) , leí la siguiente oración:

La versión clásica de (en la que las compuertas A N D y O R tienen como máximo un despliegue constante) es probablemente más débil que A C 0 .QAC0ANDORAC0

Falta una referencia para este reclamo. Llamaré a esta clase , donde b f significa "fanout limitado". (El complejo zoológico está caído y no puedo verificar si esa clase ya tiene un nombre en la literatura). Si suponemos un despliegue ilimitado para los bits de entrada, entonces este circuito parece ser equivalente a fórmulas de profundidad constante hasta un aumento polinómico en el tamaño, por lo que la afirmación anterior no tiene sentido. En cambio, si asumimos también un abanico acotado para los bits de entrada, entonces no puedo pensar en ningún lenguaje que separe esta clase de A C 0 . Un posible candidato podría ser el lenguaje X : = { x |ACbf0bfAC0 ,es decir, el lenguaje de las cadenas con solo uno 1. Es fácil mostrar X A C 0 , pero no pude demostrar que X A C 0 b f .X:={x|weight(x)=1}XAC0XACbf0

Las preguntas son:

¿Es realmente más débil que A C 0 ? Si es así, ¿alguna idea o alguna referencia sobre cómo probarlo? ¿Y qué es un idioma que separa esas dos clases? ¿Qué hay de X ?ACbf0AC0X

Alessandro Cosentino
fuente
66
El límite de abanico de bits de entrada hará que el circuito sea de tamaño lineal. Cualquier función que requiera un tamaño superlineal los separará. AC0
Kaveh
2
@Kaveh: Tal vez podría volver a publicar que, como respuesta, tal vez con un ejemplo de una función explícita que requiere de tamaño super-lineal circuitos y tal vez una referencia que muestra el tamaño límite inferior? (¿O incluya el argumento en su respuesta si es muy simple?)AC0
Robin Kothari
2
@Kaveh Gracias. No sabía que se conocía la separación entre y los circuitos de profundidad constante de tamaño lineal (aparentemente llamado L C 0 ). La referencia es "Restricciones deterministas en la complejidad del circuito" por S. Chaudhuri y J. Radhakrishnan. @Kaveh ¿Puedes responder tu comentario? AC0LC0
Alessandro Cosentino
2
Como se discutió en la pregunta de seguimiento cstheory.stackexchange.com/questions/7447/… , es lo mismo que la fórmula de tamaño lineal. ACbf0
domotorp

Respuestas:

23

Un límite de despliegue de bits y compuertas de entrada hará que el tamaño del circuito sea lineal. Deje ser un límite en el despliegue de las puertas y entradas. Es un DAG con un grado máximo limitado por k y una trayectoria máxima de longitud d . El número de cables disponibles en cada nivel puede aumentar k veces, y el número de cables disponibles en la parte superior es k n , por lo que el número total de cables en el circuito es como máximo k n d i = 0 k ik d + 1 n que es O ( n ) .kkdkknkni=0dkikd+1nO(n)

Cualquier función que requiera un tamaño superlineal separará la clase de funciones con abanico limitado (aplicado también a los bits de entrada) de A C 0 . Aquí hay unos ejemplos:AC0AC0

  1. [CR96]: una función que necesita un tamaño superlineal es el 1AC0 -selector aproximado14. A -el selector aproximado es cualquier función cuyo valor es:14

    • siempre que el número de 1 s sea como máximo n01 ,n4
    • siempre que el número de 0 s sea como máximo n10 ,n4
    • puede ser o 1 de lo contrario.01
  2. [Ros08] muestra que la -clique tiene una complejidad de funciones A C 0 n Θ ( k ) ( n 2 bits de entrada son bordes posibles de un gráfico con n vértices). Esto proporciona un tamaño de línea súper inferior para k > 2 .kAC0nΘ(k)n2nk>2

  3. Probablemente sea posible generalizar el ejemplo en 2 latas a la existencia de cualquier subestructura inducida fija no trivial (que requiera más de un bit) en una estructura desordenada dada, por ejemplo:

    • existencia de una ruta de longitud 2 en un gráfico dado,
    • ,#1(x)=2

    ya que requieren un número súper constante de compuertas dependiendo de un bit que no es posible en .ACbf0

  4. El ejemplo más fácil es una puerta duplicadora, es decir, una puerta que crea copias de su bit de entrada. Esto no es posible en A C 0 b f ya que solo O ( 1 ) de las puertas puede depender de cada bit de entrada.ω(1)ACbf0O(1)

ACbf0SkdSACbf0k2d+1nAC0ACbf0


Referencias

[CR96] S. Chaudhuri y J. Radhakrishnan, " Restricciones deterministas en la complejidad del circuito ", 1996

[Ros08] Benjamin Rossman, " Sobre la complejidad de la profundidad constante de k-Clique ", 2008

[Juk] Stasys Jukna, " Complejidad de la función booleana: avances y fronteras ", borrador

Kaveh
fuente
12
LC0AC0kkddknΩ(nk/4)AC0nkk) es en realidad infinito.
Srikanth
1
Actualicé la respuesta, gracias a Alessandro, domotorp, Robin, Srikanth y Stasys.
Kaveh
1
Ω(nlogn)
1
PkkAC02knO(1)
1
AC0