Circuito de límites inferiores sobre conjuntos arbitrarios de puertas

40

En la década de 1980, Razborov demostró que hay funciones booleanas monótonas explícitas (como la función CLIQUE) que requieren exponencialmente muchas puertas AND y OR para computar. Sin embargo, la base {AND, OR} sobre el dominio booleano {0,1} es solo un ejemplo de un conjunto de puertas interesante que no es universal. Esto lleva a mi pregunta:

¿Hay algún otro conjunto de puertas, interesantemente diferente de las puertas monótonas, para las cuales se conocen límites inferiores exponenciales en el tamaño del circuito (sin profundidad u otras restricciones en el circuito)? Si no, ¿hay algún otro conjunto de puertas que sea un candidato plausible para tales límites inferiores --- límites que no necesariamente requerirían romper la barrera de las Pruebas Naturales, como el resultado de los circuitos monótonos de Razborov no lo hizo?

Si existe tal conjunto de compuertas, entonces ciertamente estará sobre un alfabeto k-ary para k≥3. La razón es que, sobre un alfabeto binario, el

(1) puertas monótonas ({AND, OR}),

(2) puertas lineales ({NOT, XOR}), y

(3) puertas universales ({AND, OR, NOT})

básicamente agota las posibilidades interesantes, como se desprende del teorema de clasificación de Post. (Tenga en cuenta que supongo que las constantes --- 0 y 1 en el caso binario --- siempre están disponibles de forma gratuita.) Con las puertas lineales, cada función booleana f: {0,1} n → {0,1} que es computable en absoluto es computable por un circuito de tamaño lineal; con un conjunto universal, por supuesto, nos enfrentamos a Natural Proofs y las otras terribles barreras.

Por otro lado, si consideramos los conjuntos de compuertas sobre un alfabeto de 3 o 4 símbolos (por ejemplo), entonces se abre un conjunto más amplio de posibilidades --- y al menos que yo sepa, esas posibilidades nunca se han delineado completamente desde el punto de vista de la teoría de la complejidad (corríjame si me equivoco). Sé que los posibles conjuntos de puertas se estudian ampliamente bajo el nombre de "clones" en álgebra universal; Desearía estar más familiarizado con esa literatura para saber qué significan los resultados de esa área para la complejidad del circuito.

En cualquier caso, no parece descabellado que haya otros límites inferiores del circuito dramático maduros para la prueba, si simplemente expandimos la clase de conjuntos de puertas sobre alfabetos finitos que estamos dispuestos a considerar. Si me equivoco, ¡por favor dime por qué!

Scott Aaronson
fuente
3
Si considera las funciones , entonces la situación es más complicada para las puertas lineales, porque el argumento de conteo muestra que hay funciones que requieren Ω ( n 2f:{0,1}n{0,1}ncompuertas para computar, aunque hasta donde yo sé no hay ejemplos explícitos de funciones que requieran circuitos de tamaño superlineal. Ω(n2log(n))
Grigory Yaroslavtsev
2
Solo una nota: si reemplaza las puertas booleanas monótonas con puertas que calculan cualquier función real no decreciente , también obtendrá límites inferiores exponenciales en el tamaño de los circuitos. Esto fue demostrado por Pudlak: límites inferiores para resolución y corte de planos, pruebas y cálculos monótonos , J. of Symb. Logic 62 (3), 1997, págs. 981-998.
Iddo Tzameret
2
Grigory: gracias; ¡Discutí si mencionar eso en el OP! Tiene razón en que no tenemos ningún límite inferior superlineal explícito en el número de puertas XOR necesarias para calcular una función lineal f: {0,1} <sup> n </sup> & rarr; {0,1} < sup> n </sup>. Por otro lado, no es difícil encontrar candidatos para transformaciones lineales que <i> deberían </i> requerir & Omega; (n log n) compuertas XOR (la Transformada de Fourier, la matriz "Junta de Sierpinski" ...) , y Bram Cohen propuso una función de ejemplo que debería requerir puertas XOR & Omega (n <sup> 3/2 </sup>) (no lo recuerdo, pero podría preguntarle).
Scott Aaronson
Incluso para el tamaño del alfabeto 3, la red de clones es incontable y contiene cada red finita como una red secundaria. Por lo tanto, hay infinitas bases de operaciones posiblemente interesantes para considerar. No conozco ningún trabajo sobre el uso de clones no booleanos para los límites inferiores del circuito, pero parece que vale la pena investigarlo con más profundidad.
András Salamon
3
Scott, ¿conoces un análogo apropiado para la clase AC ^ 0 sobre aphabets más grandes? Permítanme también comentar que uno puede considerar nociones de monotonicidad para alfabetos más grandes (Elchanan Mossel y yo escribimos acerca de umbrales agudos para esos front.math.ucdavis.edu/1011.3566 ) así que tal vez el teorema de Rasborov se extiende para cirujanos monótonos sobre alfabeto más grande para cierta noción de monotonicidad
Gil Kalai

Respuestas:

25

(Movido de los comentarios como sugirió Suresh. Tenga en cuenta que algunos errores en el comentario se corrigen aquí).

Gracias a Scott por una gran pregunta.

Scott parece sugerir que la razón de la dificultad de los límites inferiores puede ser el lenguaje restringido de las operaciones en el caso booleano. El argumento de conteo de Shannon que muestra que la mayoría de los circuitos debe ser grande se basa en la brecha entre el poder expresivo contable y muchos circuitos. Esta brecha parece desaparecer cuando el alfabeto tiene al menos 3 símbolos.

Para el tamaño del alfabeto 2 (el caso booleano), la red de clones es infinitamente contable y se llama red de Post .

Imagen de celosía de la publicación de Wikipedia

La red de Post también deja en claro por qué solo hay unas pocas bases de operaciones interesantes para el caso booleano.

Para el tamaño del alfabeto 3 o mayor, la red de clones es incontable. Además, la red no satisface ninguna identidad de red no trivial, por lo que parece imposible proporcionar una descripción completa de la red. Para el tamaño del alfabeto 4 o mayor, la red de clones en realidad contiene cada red finita como una sub red. Entonces, hay infinitas bases de operaciones posiblemente interesantes para considerar cuando el alfabeto tiene 3 o más símbolos.

  • Bulatov, Andrei A., Condiciones satisfechas por retículos clon , Álgebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Scott preguntó además: ¿la red de clones sigue siendo incontable si asumimos que las constantes están disponibles de forma gratuita?

La respuesta es que sí, ver por ejemplo

  • Gradimir Vojvodić, Jovanka Pantović y Ratko Tošić, El número de clones que contienen una función unaria , NSJOM 27 83–87, 1997. ( PDF )
  • J. Pantović, R. Tošić y G. Vojvodić, La cardinalidad de álgebras funcionalmente completas en un conjunto de tres elementos , Algebra Universalis 38 136–140, 1997. doi: 10.1007 / s000120050042

aunque aparentemente esto fue publicado anteriormente:

  • Ágoston, I., Demetrovics, J. y Hannák, L. Sobre el número de clones que contienen todas las constantes , Coll. Mates. Soc. János Bolyai 43 21-25, 1983.

Una buena declaración específica es de:

  • A. Bulatov, A. Krokhin, K. Safin y E. Sukhanov, Sobre la estructura de las redes clónicas , en: "Álgebra general y matemática discreta", editores: K. Denecke y O. Lueders, 27–34. Heldermann Verlag, Berlín, 1995. ( PS )

k3Lk20

Para concluir, no conozco ningún trabajo sobre el uso de clones no booleanos para los límites inferiores del circuito. Parece que vale la pena investigarlo con más profundidad. Dado lo relativamente poco que se sabe sobre la red de clones, puede haber bases interesantes de operaciones que esperan ser descubiertas.

Más vínculos entre la teoría de los clones y la informática probablemente también sean de gran interés para los matemáticos que trabajan en álgebra universal. Un ejemplo previo de este tipo de interacción surgió cuando Peter Jeavons demostró que las álgebras podrían estar asociadas con lenguajes de restricción, de una manera que permite traducir los resultados de trazabilidad a las propiedades del álgebra. Andrei Bulatov usó esto para demostrar la dicotomía para CSP con tamaño de dominio 3. En el otro sentido, ha habido un resurgimiento en el interés por la teoría de la congruencia domesticada como resultado de la aplicación informática. Me pregunto qué seguiría de un vínculo entre la teoría de los clones y la complejidad de los circuitos no booleanos.

András Salamon
fuente
Muchas gracias, András! Revisaré el artículo de Ágoston et al. cuando tenga la oportunidad Mientras tanto, revisé la lista de clones precompletos máximos en un conjunto de 3 elementos de Pantović et al. papel al que se vinculó, y no creo que ninguno de ellos sea candidato para "nuevos" límites inferiores del circuito. (Para algunos de ellos, los límites inferiores exponenciales se siguen inmediatamente del límite inferior monótono de Razborov; para otros, necesitaríamos límites inferiores para circuitos generales o para circuitos lineales.) Pero incluso en el caso k = 3, los clones son más pequeños que los precompletos Todavía parece que vale la pena mirarlo.
Scott Aaronson
15

Esto se mueve de los comentarios, como sugirió Suresh.

f:0,1n0,1nΩ(n2log(n))

n2log(n)cc

Ω(nlogn)Ω(n3/2)

Edición 2. El obstáculo principal es que no tenemos ningún método para probar los límites inferiores no lineales, incluso para puertas lineales, que yo sepa (para los límites inferiores lineales uno puede usar la eliminación de la puerta, es muy poco probable que no -límites lineales). Aunque parece que algunos métodos de álgebra lineal realmente deben ser útiles. Así que encontrar candidatos es bueno, pero de todos modos se necesitan algunos métodos nuevos.

Grigory Yaroslavtsev
fuente
11
  1. {0,1}aZ3n={0,1,2}nmin(x,y)xymod2f(a)=0a02's en es al menos el número de ' s. Muestra que cualquier circuito (sobre esa base MIN / XOR) requiere aproximadamente compuertas para calcular . Pero eso fue! No tengo conocimiento de ningún resultado adicional en un favor similar (ir a dominios más grandes, pero aún finitos), excepto, por supuesto, la materia de los circuitos aritméticos. Pero solo para los circuitos: para que el programa de ramificación vaya a dominios más grandes, facilita la tarea de los límites inferiores. a12n/nf

  2. En circuitos con puertas XOR. Aquí incluso el caso de la profundidad está ampliamente abierto. Los límites inferiores más altos para las transformaciones lineales explícitas sobre tienen la forma . Probar un límite como para una constante , incluso en profundidad e incluso si solo se permiten puertas XOR, es un desafío.2y=AxGF(2)nlog3/2nn1+cc>02

Stasys
fuente
2
Estimado Stasys, ¿puedo sugerirle que registre su cuenta? Le permitirá usar la misma cuenta de usuario para publicar respuestas y editarlas más tarde, entre otras cosas. (Déjame saber si usted decide registrarse y voy a fusionar sus cuentas anteriores con él por lo que también puede editar sus mensajes anteriores.)
Kaveh
1
Gracias, Kaveh, me registré ahora. La sugerencia de Scott (ir a dominios más grandes) también puede ser interesante desde un punto de vista "pragmático". Digamos, ¿cuál es el número más pequeño de compuertas max / plus en un circuito para el problema Subset-Sum con la capacidad de la mochila ? Para simular el algoritmo de programación dinámica estándar, es suficiente permitir que los cables realicen pruebas para enteros en nuestro dominio. Este algoritmo también proporciona un límite superior en el número de puertas. Problema: pruebe que las compuertas son necesarias. Esto significaría que DP no puede hacerlo mejor para Knapsack. Kxi=aanKΩ(nK)
Stasys