¿El no determinismo es en promedio inútil para los circuitos?

Savický y Woods (El número de funciones booleanas calculadas por fórmulas de un tamaño dado) demuestran el siguiente resultado.

Teorema [SW98]: Para cada constante , casi todas las funciones booleanas con complejidad de fórmula como máximo tienen complejidad de circuito al menos . $k>1$ $n^k$ $n^k/k$

La prueba consiste en derivar un límite inferior en , el número de funciones booleanas en entradas calculadas por fórmulas de tamaño . Al comparar con el número de circuitos de tamaño , que es a lo sumo , puede darse cuenta de que para grande , $B(n,n^k)$ $n$ $n^k$ $B(n,n^k)$ $C = n^k/k$ $C^{C}e^{C+4n}$ $n$ , y el resultado sigue. $C^{C}e^{C+4n} << B(n,n^k)$

Me parece que el resultado podría fortalecerse al observar que el número de circuitos no deterministas de tamaño con entradas no deterministas no es mucho mayor que el número de circuitos deterministas de tamaño (para no demasiado grande, digamos ) Por lo tanto, creo que el siguiente corolario es válido: $n^k$ $m$ $n^k$ $m$ $m=n$

Corolario: por cada constante , casi todas las funciones booleanas con complejidad de fórmula como máximo tienen una complejidad de circuito no determinista al menos (para circuitos no deterministas con entradas no deterministas). $k>1$ $n^k$ $n^k/k$ $n$

$x = (x_1,\dots,x_n)$ $y=(y_1,\dots,y_m)$ $C$ $x$ $y$ $1$ $(x,y)$

$B(n,n^k)$ $n$ $n^k$ $n^k$ $n^k$

Preguntas:

(1) ¿Hay implicaciones / consecuencias interesantes del corolario anterior?

(2) ¿Hay otros resultados en la misma dirección? Por ejemplo, ¿qué se sabe sobre la siguiente proposición? Para problemas en P, el cambio de TM a NTM no puede, en promedio, disminuir la complejidad en más de un factor constante.

(Gil Kalai también tiene una pregunta algo relacionada con esta).

cc.complexity-theory circuit-complexity nondeterminism Gustav Nordh
fuente

Respuestas:

$2^k$ $k$

2) Para clases uniformes como P esto es más desafiante, ya que no existe una definición clara de "función promedio en P" y los argumentos de conteo ya no funcionan tan limpiamente. Es coherente con el conocimiento actual de que todo en P puede resolverse en un tiempo lineal no determinista.

Lance Fortnow
fuente

¿Tiene algún puntero para esta última afirmación sobre P y NTIME (n)?

Quise decir que es un problema abierto si P está contenido en NTIME (n). El problema se discute en un documento de Ravi Kannan ( doi.org/10.1145/800061.808764 ).

Lance Fortnow

P ⊈ N T I M E (n^{α})

$P\not\subseteq NTIME(n^\alpha)$

α \in (0, 1)

$\alpha\in(0,1)$

α

$\alpha$

Creo que la función de paridad no se puede calcular en NTIME ( ) para cualquier . De lo contrario, tendría circuitos de profundidad-2 de tamaño para una paridad que no puede suceder.

n^{α}

$n^\alpha$

α < 1

$\alpha<1$

2^{o (n)}

$2^{o(n)}$

Lance Fortnow

@LanceFortnow Parece entonces que ?

P ⊈ \exists (\log n) T I M E [p o l y l o g (n)]

$P\not\subseteq \exists(\log n)TIME[polylog(n)]$

T ....