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?
la source
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
la source