Teorema de jerarquía para el tamaño del circuito

Creo que un teorema de jerarquía de tamaño para la complejidad del circuito puede ser un gran avance en el área.

¿Es un enfoque interesante para la separación de clases?

La motivación para la pregunta es que tenemos que decir

hay alguna función que no puede calcularse mediante circuitos de tamaño y puede calcularse mediante un circuito de tamaño donde . (y posiblemente algo relacionado con la profundidad)g ( n ) f ( n ) < o ( g ( n ) $f(n)$$g(n)$$f(n)<o(g(n))$

entonces, si , la propiedad parece no ser natural (viola la condición de amplitud). Claramente, no podemos usar la diagonalización, porque no estamos en un entorno uniforme.$f(m)g(n) \leq n^{O(1)}$

¿Hay un resultado en esta dirección?

De hecho, es posible demostrar que, por cada $f$ suficientemente pequeña (menos de ), hay funciones computables por circuitos de tamaño pero no por circuitos de tamaño , o incluso , según el tipo de compuertas que permita.f ( n ) f ( n ) - O ( 1 ) f ( n ) - $2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Aquí hay un argumento simple que muestra que hay funciones computables en tamaño pero no en tamaño .f ( n ) - O ( n $f(n)$$f(n)-O(n)$

Lo sabemos:

1. existe una función que requiere una complejidad de circuito de al menos y, en particular, una complejidad de circuito mayor que .2 n / O ( n ) f ( n $g$$2^n/O(n)$$f(n)$
2. la función tal que para cada entrada es computable por un circuito de tamaño constante.z ( x ) = 0 $z$$z(x)=0$$x$
3. si dos funciones y difieren solo en una entrada, entonces su complejidad de circuito difiere en a lo másg 2 O ( n $g_1$$g_2$$O(n)$

Suponga que no es cero en entradas. Llame a tales entradas . Podemos considerar, para cada , la función que es la función indicadora del conjunto ; así y .$g$$N$$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Claramente, hay algunos tales que tiene una complejidad de circuito mayor que y tiene una complejidad de circuito menor que . Pero entonces tiene una complejidad de circuito menor que pero mayor que .g i + 1 f ( n ) g i f ( n ) g i f ( n ) f ( n ) - O ( n $i$$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Este resultado puede probarse usando un argumento de conteo simple. Considere una función aleatoria aplicada a los primeros bits de la entrada. Es casi seguro que esta función tiene complejidad de circuito ( 1 + o ( 1 ) ) ( 2 k / k ) según el argumento de conteo de Riordan y Shannon, y coincide con los límites superiores. Por lo tanto, seleccionando k de modo que 2 g ( n ) < 2 k / k < f ( n ) / 2 podamos distinguir el tamaño $k$$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ del tamaño f ( n ) . Tenga en cuenta que las funciones en cuestión ni siquiera serán necesariamente computables, pero podemos colocarlas en la jerarquía de tiempo exponencial mediante técnicas estándar (siempre que podamos calcular el valor correcto de k ). Por supuesto, no podemos probar ningún límite mayor que 2 n / n , porque esa es la complejidad del circuito en el peor de los casos de cualquier función. $g(n)$$f(n)$$k$$2^n/n$

Las pruebas naturales no se aplican a este tipo de argumento, porque la propiedad en cuestión es `` no tener un circuito pequeño '', que no es fácilmente computable desde la tabla de verdad de la función (presumiblemente). No está claro qué tan bajo en clases de complejidad puede llegar este tipo de conteo. ¿Hay alguna razón por la que no podamos usar un argumento de conteo para probar límites inferiores para ? No que yo sepa. $NE$