Polynômes explicites en 1 variable avec des limites inférieures de complexité de circuit superlogarithmique?

En comptant les arguments, on peut montrer qu'il existe des polynômes de degré n dans 1 variable (c'est-à-dire quelque chose de la forme qui ont complexité du circuit n. De plus, on peut montrer qu'un polynôme comme nécessite au moins multiplications (vous en avez besoin juste pour obtenir un degré suffisamment élevé). Existe-t-il des exemples explicites de polynômes dans 1 variable avec une borne inférieure superlogarithmique sur la complexité? (les résultats sur n'importe quel domaine seraient intéressants) $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 mats
la source

Les exemples que vous avez en tête avec la complexité du circuit sur un champ fini? Je ne vois pas comment un argument de comptage fonctionnerait sur un champ infini, et sur les raisonnements, je suis presque sûr que la liaison Paterson-Stockmeyer est étroite (voir aussi ma réponse ci-dessous).

n

$n$

\sqrt{n}

$\sqrt{n}$

Joshua Grochow

La borne sqrt (n) que vous mentionnez n'est qu'une limite supérieure du nombre de multiplications (sur n'importe quel champ), mais si nous comptons les additions et les multiplications comme des opérations, nous avons besoin de n opérations sur un champ infini pour presque tous les polynômes, juste car il y a n coefficients distincts dans le polynôme et il n'y a aucun moyen d'évaluer tous les polynômes possibles avec moins de n opérations (je ne sais pas si cela devrait être appelé un argument de comptage ou non).

mat hastings

Je pense que vous devez être un peu plus précis dans la déclaration "il n'y a aucun moyen d'évaluer tous les polynômes possibles avec moins de n ops." Une façon d'interpréter cela est: si nous considérons le polynôme comme un polynôme non seulement en , mais traitons également les comme des variables (ou, de manière équivalente, supposons que les sont algébriquement indépendants), alors le résultat que cela nécessite n ajouts est celui de Pan (1966) et n'est pas seulement un argument de comptage (bien que ce ne soit pas trop difficile). Sinon, je ne suis pas sûr du résultat auquel vous faites référence avec cette déclaration.

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

Joshua Grochow

Ce que je veux dire, c'est que le circuit se compose de portes d'addition et de multiplication. Les entrées pour une porte donnée peuvent être des sorties de portes précédentes, ou x, ou certaines constantes. La question est: pour un polynôme donné, peut-on trouver un circuit et un choix de constantes dans ce circuit pour le calculer? Mais, nous avons un espace (n + 1) dimensionnel de polynômes, mais si nous fixons la structure d'un circuit avec moins de n portes (par "structure", je veux dire quelles portes utilisent des sorties dont d'autres portes) et considérons toutes choix possibles de constantes cela donne moins d'un espace à n dimensions de polynômes qui peuvent être calculés.

mat hastings

Btw --- l'impression que j'ai est que la construction d'exemples explicites sur R ou C sans autres restrictions sur les coefficients est principalement résolue. En revanche, en construisant des exemples explicites où tous les coefficients a_i sont des entiers et qui ne croissent pas trop rapidement, ça reste ouvert? Il y a un exemple avec toutes les constantes entières dans l'enquête que vous mentionnez, mais elles croissent doublement exponentiellement.

mat hastings

Paterson et Stockmeyer montrent que pour la plupart des nombres de nombres rationnels , l'évaluation de nécessite l' arithmétique opérations, et cela est serré. $n$ $(a_1, \dotsc, a_n)$ $\prod_{i=1}^{n} (x - a_i)$ $\Omega(\sqrt{n})$

Les polynômes suivants obtiennent dans un facteur logarithmique de la borne , par les résultats de Strassen, Schnorr et Heintz & Sieveking: , , (pour un rationnel qui n'est pas un entier), etc. Pour des références exactes et pour plus d'informations, voir pp. 324-325 de l'enquête de von zur Gathen . $\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
la source

Merci. Ainsi, il semblerait que le problème ouvert soit que si vous comptez également les ajouts comme des opérations, peut-on construire un polynôme qui a besoin de plus de sqrt (n) opérations, dans le but d'en construire un qui a besoin de n opérations. Des résultats à ce sujet? (J'en doute, car dans la méthode qui n'a besoin que de multiplications sqrt (n), les ajouts donnent une certaine multiplication matricielle et cela se réduit probablement à des limites inférieures sur la complexité d'une multiplication matrice-scalaire)

mat hastings

Polynômes explicites en 1 variable avec des limites inférieures de complexité de circuit superlogarithmique?

Réponses: