¿Polinomios explícitos en 1 variable con complejidad de circuito superlogarítmico límites inferiores?

Al contar los argumentos, se puede mostrar que existen polinomios de grado n en 1 variable (es decir, algo de la forma que tienen complejidad de circuito n. Además, uno puede mostrar que un polinomio como requiere al menos multiplicaciones (lo necesita solo para obtener un grado lo suficientemente alto). ¿Hay ejemplos explícitos de polinomios en 1 variable con un límite inferior superlogarítmico en la complejidad? (los resultados sobre cualquier campo serían interesantes) $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ $x^n$ $\log_2 n$

cc.complexity-theory circuit-complexity polynomials algebraic-complexity hastings mate
fuente

¿Son los ejemplos que tiene en mente con la complejidad del circuito

sobre un campo finito? No veo cómo funcionaría un argumento de conteo en un campo infinito, y sobre los racionales, estoy bastante seguro de que

Paterson-Stockmeyer

n

$n$

\sqrt{n}

$\sqrt{n}$

El límite sqrt (n) que mencionas es solo un límite superior en el número de multiplicaciones (sobre cualquier campo), pero si contamos tanto las sumas como las multiplicaciones como operaciones, entonces necesitamos n operaciones sobre un campo infinito para casi todos los polinomios, solo porque hay n coeficientes distintos en el polinomio y no hay forma de evaluar todos los polinomios posibles con menos de n operaciones (no estoy seguro de si esto debería llamarse argumento de conteo o no).

Matt Hastings

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

Lo que quiero decir es: el circuito consta de compuertas de suma y multiplicación. Las entradas para una puerta determinada pueden ser salidas de puertas anteriores, o x, o algunas constantes. La pregunta es: para un polinomio dado, ¿podemos encontrar un circuito y la elección de constantes en ese circuito para calcularlo? Pero, tenemos un espacio (n + 1) -dimensional de polinomios, pero si arreglamos la estructura de un circuito con menos de n compuertas (por "estructura", me refiero a qué compuertas usan salidas de qué otras compuertas) y consideramos todos posibles elecciones de constantes, esto da menos de un espacio tridimensional de polinomios que se pueden calcular.

Matt Hastings

Por cierto, la impresión que tengo es que la construcción de ejemplos explícitos sobre R o C sin más restricciones en los coeficientes se resuelve principalmente. Por otro lado, al construir ejemplos explícitos donde todos los coeficientes a_i son enteros y no crecen demasiado rápido, ¿aún se abre? Hay un ejemplo con todas las constantes enteras en la encuesta que menciona, pero crecen doblemente exponencialmente.

Matt Hastings

$n$ $(a_1, \dotsc, a_n)$ $\prod_{i=1}^{n} (x - a_i)$ $\Omega(\sqrt{n})$

$\sqrt{n}$ $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$ $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$ $\sum_{i=1}^{n} i^{r} x^{i}$ $r$

Joshua Grochow
fuente

Gracias. Entonces, parece que el problema abierto es que si cuenta las adiciones también como operaciones, ¿se puede construir un polinomio que necesite más que operaciones sqrt (n), con el objetivo de construir uno que necesite n operaciones. ¿Algún resultado para esto? (I dudo, porque en el método que necesita sólo sqrt n) multiplicaciones (, las adiciones dan algunos multiplicación de la matriz y esto probablemente reduce para disminuir los límites de la complejidad de una multiplicación matriz-escalar)

mate Hastings

¿Polinomios explícitos en 1 variable con complejidad de circuito superlogarítmico límites inferiores?

Respuestas: