¿Cuál es la clase de complejidad "más pequeña" para la que se conoce un circuito superlineal?

25

Disculpas por hacer una pregunta que seguramente debe estar en muchas referencias estándar. Tengo curiosidad acerca de exactamente la pregunta en el título, en particular estoy pensando en los circuitos booleanos, sin límite de profundidad. Pongo "el más pequeño" entre comillas para permitir la posibilidad de que haya varias clases diferentes, que no se incluyen entre sí, para las cuales se conoce un límite superlineal.

hastings mate
fuente

Respuestas:

25

Creo que las clases más pequeñas conocidas son S2P (Cai, 2001), PP (Vinodchandran, 2005) y (MAcoMA)/1 (Santhanam, 2007). De hecho, se sabe que todos estos no están en SIZE(nk) para cada constante k .

Ryan O'Donnell
fuente
1
Gracias por todas las respuestas. Estoy aceptando Ryan porque tiene la mayor variedad de resultados, pero gracias Robin y Kaveh por las explicaciones detalladas.
Matt Hastings
20

El resultado más fuerte que conozco es que para todos los k, hay un problema en S2P que requiere circuitos de tamaño Ω(nk) .

es una clase contenida en Z P P N P , que está contenida en Σ P 2Π P 2 . (Elzoológico de complejidadtiene más información sobre esta clase).S2PZPPNPΣ2PΠ2P

El resultado se desprende de la versión más fuerte del teorema de Karp-Lipton debido a Cai .

Una prueba rápida de cómo esto se deduce del teorema de KL: Primero, si SAT requiere circuitos de tamaño súper polinomiales, hemos terminado, ya que hemos exhibido un problema en que necesita circuitos de tamaño súper polinomiales. Si SAT tiene circuitos de tamaño polinomial, entonces, según la versión más fuerte del teorema de Karp-Lipton, PH colapsa a S P 2 . Sabemos que PH contiene problemas tales problemas (por el resultado de Kannan), y por lo tanto S P 2 contiene tal problema.S2PS2PS2P

Robin Kothari
fuente
3
Una respuesta agradable y superior como siempre. :)
Kaveh
13

Para circuitos generales, sabemos que hay problemas en que requieren circuitos de tamaño Ω ( n k ) , esto se debe a Ravi Kannan (1981) y se basa en su resultado de que P H contiene tales problemas .Σ2pΠ2pΩ(nk)PH

Creo que los mejores límites inferiores para todavía están alrededor de 5 n .NP5n

Vea el libro de Arora y Barak, página 297. Richard J. Lipton tenía una publicación en su blog sobre estos resultados, también vea este .

Kaveh
fuente
1

S2Pk1c
O~(nk)
O2PO~(nk2)O(nk(logn)c)

O2PO~(nk2+k)iO~(nmin(k2+k,k3))

Un problema de decisión no computable con los circuitos io- es el menor número (consultado usando sus dígitos binarios) que no es la tabla de verdad de un circuito con puertas. Si NP está en P / poli, el problema tiene un testigo ajeno irrefutable que consiste en lo siguiente: (1) (2) un circuito que dado , muestra que tiene un circuito suficientemente pequeño. (3) (solo se usa para el límite ) un verificador que nos permite ejecutar el circuito del oponente por (2) solo veces (obteniendo 1 bit por carrera )N n k( log n ) c + 1N N < N N ˜ O ( n k 3 ) O ( 1 )O(nk(logn)c)Nnk(logn)c+1
N
N<NN
O~(nk3)O(1)

En una nota separada, por cada , hay problemas de decisión en (MA ∩ coMA) / 1 que no tienen circuitos . '/ 1' significa que la máquina recibe un consejo que depende solo del tamaño de entrada. Además, la cadena de Merlin envía puede ser elegido a depende sólo del tamaño de entrada (con esta restricción, MA es un subconjunto de ), y el consejo complejidad . La prueba (Santhanam 2007) generaliza IP = PSPACE y PSPACE⊂P / poly ⇒ PSPACE = MA mediante el uso de un cierto problema PSPACE-complete que se comporta bien y rellena las entradas para obtener tamaños de circuito mínimos que son infinitamente frecuentes entre y , usando consejos para detectar suficientes ejemplos de talesO ( n k ) O 2 P Σ P 2 n k + 1 n k + 2 n nkO(nk)O2PΣ2Pnk+1nk+2n, y para estos , resolver el problema acolchado haciendo que Merlin produzca dicho circuito.n

Dmytro Taranovsky
fuente