Complexité de la réduction de la taille des formules polynomiales

28

Soit un polynôme de degré d dans n variables sur F 2 , où d est constant (disons 2 ou 3). Je voudrais trouver la plus petite formule pour f , où «formule» et «taille de formule» sont définies de manière évidente (par exemple, la plus petite formule pour le polynôme x 1 x 2 + x 1 x 3 est x 1 ( x 2 + x 3 ) ).f(x1,,xn)dnF2dfx1x2+x1x3x1(x2+x3)

Quelle est la complexité de ce problème - est-il difficile à NP? La complexité dépend-elle de ?d

[Plus formellement, une formule (alias "formule arithmétique") est un arbre binaire enraciné, dont chacune des feuilles est étiquetée avec une variable d'entrée ou la constante 1. Tous les autres sommets de l'arbre sont étiquetés avec ou × . La taille de la formule est le nombre de feuilles utilisées. La formule calcule un polynôme récursivement: + sommets calculent la somme de leurs enfants sur F 2 , × sommets calculent le produit. ]+×+F2×

Ashley Montanaro
la source
1
ne pouvons-nous pas réduire les tests d'identité polynomiale à ce problème?
Kaveh
4
Je suppose qu'il peut y avoir un lien, mais je ne le vois pas immédiatement - en particulier en raison de la contrainte sur le degré. De plus, si le problème est plus difficile que le test d'identité polynomiale, il serait intéressant de savoir combien plus difficile.
Ashley Montanaro
Dans votre cas, comment le nombre de portes ( s et × s) dans la formule est-il lié à la taille réelle de la formule? Pour d = 2 , la construction dans Ehrenfeucht et Karpinski 90 semble être pertinente (voir paragraphe 2XOR) pour la taille de la formule "gate", mais je dois y penser plus longtemps. +×d=2
Alessandro Cosentino
Comme la formule est un arbre binaire, la définition de la taille de formule que j'ai utilisée ici (nombre de feuilles) est égale au nombre de portes (sommets internes) plus un. Mais je serais intéressé par les résultats pour toute autre définition raisonnable de la taille de la formule. Je ne suis pas sûr de voir un lien avec les résultats d'Ehrenfeucht et Karpinski, car il s'agit de la complexité des solutions de comptage, plutôt que de minimiser la taille de la formule ...
Ashley Montanaro
Afin de compter le nombre de zéros, ils transforment d'abord la formule en une formule équivalente, que je rappelle être minimale en termes de multiplications et d'additions. Je n'ai cependant pas de preuve de cette minimalité. Encore une fois, cela ne répondrait qu'au cas . d=2
Alessandro Cosentino

Réponses:

7

Vous pouvez réduire le problème de co-NP-Complete TAUTOLOGY (étant donné une formule booléenne, est-ce une tautologie?) Au problème de la réduction de la taille de la formule (car une formule est une tautologie si elle est équivalente à VRAIE). De plus, TAUTOLOGY for 3DNFs (par analogie avec SAT for 3CNFs) est co-NP-Complete.

Dana Moshkovitz
la source
1
Si je comprends bien la question, devrait être calculé comme un polynôme et non comme une fonction. Peut-être qu'une clarification est nécessaire. f
Markus Bläser
3
Il y a une réduction probabiliste de 3SAT à la vérification, étant donné un polynôme deg-3 sur GF (2), s'il a un zéro [en regardant des combinaisons linéaires aléatoires des clauses], puis de cela à la vérification, étant donné un deg- 3 poly sur GF (2), qu'il soit tout à fait nul [en soustrayant le poly de 1].
Dana Moshkovitz,
1
Merci! Avez-vous une idée de la situation des polynômes de degré 2? De plus (bien que cela soit probablement très dense), j'ai du mal à voir comment un polynôme de degré 3 sur GF (2), écrit sous forme standard, peut être tout à fait zéro sans être le polynôme zéro. Pour être clair, j'imagine que l'entrée de mon problème est une description du polynôme lui-même, plutôt qu'une description d'un circuit calculant le polynôme.
Ashley Montanaro
2
Merci encore pour votre réponse. Je ne suis toujours pas convaincu de la chose tout-zéro, cependant; il me semble que tout polynôme à n variables sur GF (2) avec des termes poly (n) peut facilement être transformé en une forme standard où il est évident que le polynôme est nul ou non, simplement en faisant la substitution et la collecte des termes. xkx
Ashley Montanaro
4
En effet, si vous le rendez multilinéaire comme vous le décrivez, un polynôme est évalué à zéro sur chaque entrée si c'est le polynôme zéro. Une preuve: sélectionnez un monôme M non nul de degré minimal. Mettez à zéro toutes les autres variables. Le seul monôme survivant est M. En définissant les vars en M sur 1, vous obtenez une sortie non nulle.
Manu
4

Pas exactement la réponse, mais j'espère que cela aide:

Cette question devrait déjà être NP difficile pour d = 2 si vous voulez connaître la formule minimale pour polynômes et pas seulement pour un. La preuve est la suivante: il existe une correspondance un à un entre n formules bi-linéaires (formules de type a i j x i y j ) et les matrices tensorielles 3 c'est-à-dire les éléments en F n 2F n 2F n 2 . Telle que le rang tensoriel de la matrice est exactement la complexité de multiplication de n formules bi-linéaires.naijxiyjF2nF2nF2n

Il est connu que le rang de tenseur est un problème NP-difficile (approximativement le rang de tenseur est également NP-difficile). Ainsi, la complexité de multiplication de n formules bi-linéaires est un problème NP-difficile3n

Klim
la source
2
Merci! C'est une perspective intéressante sur le problème.
Ashley Montanaro
Le théorème suivant permet de passer de plusieurs polynômes à un pollynôme: LEt S (f) la complexité d'un polynôme puis la complexité du calcul de toutes ses dérivées est au plus de 5S (f). Ainsi, les polynômes de complexité sont presque égaux à la complexité de z 1 f 1 + z 2 f 2z n f nf1,f2,,fnz1f1+z2f2znfn
Klim
Si vous parlez de rang de tenseur, alors vous ne comptez que les multiplications mais pas les additions. Le cas et une seule forme bilinéaire est alors facile, car on peut calculer le rang d'une forme bilinéaire, en utilisant les théorèmes de structure mentionnés dans la réponse de Ramprasad. (Les preuves de ces théorèmes sont algorithmiques, voir le livre de Lidl & Niederreiter.)d=2
Markus Bläser
2

Toute réponse à cela dépend énormément du vocabulaire que vous autorisez dans la réponse. Si vous voulez que votre réponse soit dans la même langue que l'entrée (c'est-à-dire en tant que polynôme), cela conduit à un ensemble de réponses, ce avec quoi d'autres affiches ont eu du mal.

Mais si vous permettez à votre vocabulaire de réponse d'être élargi, des choses merveilleuses peuvent se produire. Vous pouvez voir un exemple dans la différenciation symbolique vs automatique: dans la différenciation symbolique, on ne permet que les «expressions», qui ont tendance à exploser assez mal; en différenciation automatique, on permet des programmes en ligne droite dans la réponse (même si l'entrée était une expression), ce qui aide grandement à contrôler le gonflement de l'expression. Pour les polynômes univariés, James Davenport et moi avons réfléchi que vous devez également ajouter des polynômes cyclotomiques dans votre vocabulaire de base (voir les références expliquant pourquoi ces polynômes semblent être la seule véritable source d'explosion, ainsi que les articles qui montrent divers résultats de réductibilité entre les problèmes polynomiaux et 3SAT).

En d'autres termes, si vous vous permettez de varier un peu ce que vous considérez comme une réponse de la réponse classique, vous pourrez peut-être simplement obtenir une réponse assez différente, c'est-à-dire avec une bien meilleure complexité. Cela dépend de votre motivation initiale à poser la question, qu'elle soit purement théorique ou avec une application en tête, pour décider si cette variation de vocabulaire vous convient. Dans le contexte où James et moi avons réfléchi à cela (calcul symbolique), ajuster le vocabulaire pour faire chuter la complexité est parfaitement acceptable (bien que rarement fait).

Jacques Carette
la source
La question demande la plus petite formule arithmétique, qu'elle définit ensuite clairement. Je ne suis donc pas sûr que cette réponse soit directement pertinente. En outre, la réponse ci-dessus de Dana Moshkovitz et les commentaires associés ne répondent pas correctement à la question, comme cela a déjà été reconnu dans les commentaires.
Raphael
Le point de ma réponse est que le PO pourrait ne pas se rendre compte qu'il ne pose pas nécessairement la meilleure question. La question du PO est posée en termes très classiques, mais si vous autorisez un petit écart par rapport à cela, vous obtenez des réponses assez différentes, ce qui aurait pu être tout à fait inattendu. Je comprends votre commentaire, mais je pense que le vote négatif est un peu dur.
Jacques Carette
Pourriez-vous corriger le premier paragraphe de votre réponse pour qu'il soit clair que la question n'a pas encore été répondue correctement? J'avais peur que les gens soient trompés.
Raphael
1
@Raphael: c'est fait. Et clarifié les choses également.
Jacques Carette
0

La minimisation générale des circuits / formules est certainement plus difficile que les tests d'identité, car la taille minimale de formule de toute identité est simplement nulle. Quant à savoir combien plus difficile, je n'ai pas de réponse définitive, mais peut-être les "algorithmes de reconstruction" étudiés dans les circuits / formules arithmétiques pourraient être quelque chose dans ce sens.

Dans ces cas, on vous donne une boîte noire et on vous dit que c'est une formule dans une classe (disons un circuit de profondeur 3 ). L'objectif est de construire une représentation de la Blackbox dans (quelque chose près) C . En règle générale, la plupart des résultats de reconstruction supposent des tests d'identité de boîte noire pour la classe, le caractère aléatoire et parfois d'autres types de requêtes. De tels algorithmes de reconstruction sont disponibles pour certaines classes restreintes de circuits mais pas pour toutes les classes pour lesquelles nous connaissons des PIT de boîte noire. Shpilka et Yehudayoff ont une fantastique enquête (pdf) sur les circuits arithmétiques, et l'un des chapitres est entièrement consacré aux algorithmes de reconstruction.C3C

Mais dans votre cas, vous dites que est une constante et donc même si l'entrée a été donnée sous forme de boîte noire, il existe des algorithmes de reconstruction pour les polynômes clairsemés. Alors peut-être que les commentaires ci-dessus ne sont pas trop intéressants dans ce cas.d

De plus, dans le cas de , il existe des théorèmes de structure pour les quadratiques. Sous une transformation linéaire sur les variables, tout quadratique peut être réécrit sous la forme x 1 x 2 + x 3 x 4 + . . + x 2 k - 1 x 2 k + . Cette propriété a été utilisée par Bogdanov et Viola pour construire des PRG pour des polynômes de faible degré (pdf) (Lemme 17 de leur article).d=2x1x2+x3x4+..+x2k1x2k+

Ramprasad
la source
Merci pour vos commentaires. Malheureusement, je ne vois pas comment utiliser ces idées pour résoudre le problème d'origine.
Ashley Montanaro