Polinômios explícitos em 1 variável com limites inferiores da complexidade do circuito superlogarítmico?

Contando argumentos, pode-se mostrar que existem polinômios de grau n em 1 variável (isto é, algo da forma que possui complexidade de circuito n. Além disso, pode-se mostrar que um polinômio como requer pelo menos multiplicações (você precisa disso apenas para obter um grau alto o suficiente). Existem exemplos explícitos de polinômios em 1 variável com um limite inferior superlogarítmico na complexidade? (resultados em qualquer campo seriam interessantes) $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
fonte

Os exemplos que você tem em mente com a complexidade do circuito

sobre um campo finito? Não vejo como um argumento de contagem funcionaria sobre um campo infinito, e sobre os racionais tenho certeza de que

Paterson-Stockmeyer

n

$n$

bound é apertado (veja também minha resposta abaixo).

\sqrt{n}

$\sqrt{n}$

Joshua Grochow

O limite sqrt (n) que você mencionou é apenas um limite superior no número de multiplicações (em qualquer campo), mas se contarmos tanto as adições quanto as multiplicações como operações, precisaremos de n operações em um campo infinito para quase todos os polinômios, apenas porque há n coeficientes distintos no polinômio e não há como avaliar todos os polinômios possíveis com menos de n operações (não tenho certeza se isso deve ser chamado de argumento de contagem ou não).

Matt Hastings

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

O que quero dizer é: o circuito consiste em portas de adição e multiplicação. As entradas para um determinado portão podem ser saídas de portas anteriores, ou x, ou algumas constantes. A questão é: para um determinado polinômio, podemos encontrar um circuito e uma escolha de constantes nesse circuito para computá-lo? Porém, temos um espaço (n + 1) tridimensional de polinômios, mas se fixarmos a estrutura de um circuito com menos de n portas (por "estrutura", quero dizer quais portas usam saídas das quais outras portas) e consideramos tudo opções possíveis de constantes, isso fornece menos que um espaço n dimensional de polinômios que podem ser computados.

matt hastings

Btw - a impressão que tenho é que a construção de exemplos explícitos sobre R ou C sem restrições adicionais aos coeficientes é resolvida principalmente. Por outro lado, construindo exemplos explícitos em que todos os coeficientes a_i são números inteiros e não crescem muito rapidamente, ele ainda está aberto? Há um exemplo com todas as constantes inteiras na pesquisa mencionada, mas elas crescem duplamente 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
fonte

Obrigado. Portanto, parece que o problema aberto é que, se você contar as adições também como operações, será possível construir um polinômio que precise de mais do que operações sqrt (n), com o objetivo de construir um que precise de n operações. Algum resultado para isso? (I dúvidas, porque o método em que necessita apenas de sqrt (n) multiplicações, as adições dar alguns multiplicação de matrizes e isto provavelmente reduz a diminuir limites da complexidade de uma multiplicação de matrizes-escalar)

mate Hastings

Polinômios explícitos em 1 variável com limites inferiores da complexidade do circuito superlogarítmico?

Respostas: