Méthode polynomiale pour les résultats de complexité

29

Les méthodes polynomiales , par exemple Nullstellensatz combinatoire et le théorème de Chevalley-Warning sont des outils puissants en combinatoire additive. En représentant un problème avec des polynômes appropriés, ils peuvent garantir l'existence d'une solution ou le nombre de solutions aux polynômes. Ils ont été utilisés pour résoudre des problèmes tels que des ensembles de sommes restreints ou des problèmes à somme nulle , et certains des théorèmes dans ce domaine ne peuvent être prouvés que par de telles méthodes.

Pour moi, la manière non constructive de ces méthodes est vraiment incroyable, et je suis curieux de savoir comment nous pouvons appliquer ces méthodes pour prouver toutes les inclusions et séparations intéressantes des classes de complexité (même si le résultat peut être résolu par d'autres méthodes).

Existe-t-il des résultats de complexité connus pour les prouver par des méthodes polynomiales?

Hsien-Chih Chang 張顯 之
la source

Réponses:

29

Voici quelques exemples classiques de l'utilisation de la méthode polynomiale:

En outre, l'analyse de Fourier des fonctions booléennes ( voici un excellent cours de Ryan O'Donnell ) a une énorme collection de résultats impressionnants, mon préféré étant la preuve de Kushilevitz-Mansour-Nisan du théorème de Goldreich-Levin .

Scott Aaronson avait en effet donné un cours à FOCS'08 sur " La méthode polynomiale en informatique classique et quantique (ppt) ".

J'espère que cela t'aides.

Ramprasad
la source
Wow ... tellement de résultats incroyables !! Ce sont vraiment géniaux, merci beaucoup !!
Hsien-Chih Chang 張顯 之
20

Il y a le résultat de Zeev Dvir sur le problème de Kakeya à champ fini qui a déjà été mentionné sur ce site. Zeev a utilisé la méthode polynomiale pour réduire la limite du nombre de points dans tout ensemble de points dans F ^ n (F champ fini, n nombre naturel) qui contient une ligne dans toutes les directions. Ce résultat a en fait attiré l'attention des personnes analysées sur la méthode polynomiale.

Le résultat de Zeev était motivé par la tâche de construire des extracteurs aléatoires . Cela fait partie d'un énorme effort en informatique théorique pour dérandomiser les algorithmes, et finalement montrer que P = BPP et des résultats de complexité similaires sont valables.

Voir plus dans l'enquête de Zeev: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf

Dana Moshkovitz
la source
Je n'avais pas remarqué cette connexion avant, merci !!
Hsien-Chih Chang 張顯 之