Sur la dérandomisation des tests d'identité polynomiale

Dans les tests d'identité polynomiale, nous recherchons un algorithme déterministe pour déduire l'égalité de deux polynômes . Dérandomiser des algorithmes randomisés efficaces connus et produire un algorithme déterministe efficace est un problème ouvert important. Existe-t-il un problème complet pour PIT afin que la dérandomisation des tests d'identité pour cette classe de polynômes résout ce problème ouvert? Sinon, existe-t-il des classes de polynômes où ce problème est résolu et des classes où ils sont ouverts?$g,h\in\Bbb Z[x_1,\dots,x_n]$

[tl;dr] On en sait beaucoup et c'est un domaine très actif! [/tl;dr]

Il est important de spécifier la représentation des polynômes d'entrée, puisqu'ils sont donnés sous forme de listes de coefficients ou de monômes non nuls, le problème est trivial. Ainsi, on suppose généralement que les polynômes sont donnés sous forme de circuits arithmétiques (alias programmes linéaires). Et le cas général se résume en fait à tester si un polynôme donné est le polynôme zéro.

Deux paramètres principaux ont été étudiés: le cas de la boîte blanche dans lequel on a le circuit arithmétique et peut l'inspecter, et le cas de la boîte noire dans lequel on sait certaines choses sur le circuit (taille, degré formel, ...) mais ne peut pas l'inspecter, l'évaluer uniquement sur certaines valeurs.

Voici quelques-unes des restrictions sur les circuits qui ont été étudiées:

• Profondeur bornée: la profondeur d'un circuit est le chemin le plus long entre une entrée et la porte de sortie. Tester des circuits de profondeur est trivial, la profondeur est très bien comprise (complètement résolue? Je ne sais pas ...), la profondeur est également bien comprise. Des résultats montrent que la résolution du problème des circuits en profondeur et en profondeur est presque la même que la résolution du cas général.$2$$3$$4$$3$$4$
• Fan-in haut / bas: pour les circuits à profondeur limitée, de nombreux résultats ont été prouvés lorsque le fan-in (ou l'arité, c'est-à-dire le nombre d'entrées à une porte donnée) de la porte supérieure ou des portes inférieures est limité.
• D'autres restrictions telles qu'une limite au nombre de fois où une variable est utilisée ont également été étudiées.

Cette enquête de Nitin Saxena est une bonne source pour ces résultats. Notez cependant qu'il a déjà plus d'un an (!), Et c'est un domaine très actif. Les résultats les plus récents ne sont donc pas couverts.

Enfin, il existe des liens entre la dérandomisation de PIT et la dérandomisation d'autres problèmes:

• Lemme de normalisation de Noether , par Ketan D. Mulmuley;
• Factorisation polynomiale multivariée , par Swastik Kopparty, Shubhangi Saraf et Amir Shpilka.