Método polinomial para resultados de complexidade

29

Os métodos polinomiais , como os teoremas Combinatorial Nullstellensatz e Chevalley – Warning, são ferramentas poderosas na combinatória aditiva. Ao representar um problema com polinômios adequados, eles podem garantir a existência de uma solução ou o número de soluções para os polinômios. Eles foram usados ​​para resolver problemas como subconjuntos restritos ou problemas de soma zero , e alguns dos teoremas dessa área só podem ser provados por esses métodos.

Para mim, a maneira não construtiva desses métodos é realmente incrível, e estou curioso para saber como podemos aplicar esses métodos para provar inclusões e separações interessantes de classes de complexidade (mesmo que o resultado possa ser resolvido por outros métodos).

Existe algum resultado de complexidade conhecido que possa ser provado por métodos polinomiais?

Hsien-Chih Chang 張顯 之
fonte

Respostas:

29

Alguns exemplos clássicos do uso do método polinomial são:

Além disso, a análise de Fourier das funções booleanas ( aqui é um ótimo curso de Ryan O'Donnell ) tem uma enorme coleção de resultados impressionantes, o meu favorito é a prova de Kushilevitz-Mansour-Nisan do teorema de Goldreich-Levin .

Scott Aaronson havia de fato dado um tutorial no FOCS'08 sobre o " Método Polinomial na Computação Clássica e Quântica (ppt) ".

Espero que isto ajude.

Ramprasad
fonte
Uau ... tantos resultados surpreendentes !! Estes são realmente incríveis, muito obrigado !!
Hsien-Chih Chang,
20

Há o resultado de Zeev Dvir no problema de Kakeya de campo finito que foi mencionado neste site anteriormente. Zeev usou o método polinomial para limitar o número de pontos em qualquer conjunto de pontos em F ^ n (campo finito F, n número natural) que contém uma linha em todas as direções. Esse resultado realmente chamou a atenção das pessoas em análise para o método polinomial.

O resultado de Zeev foi motivado pela tarefa de construir extratores de aleatoriedade . Isso faz parte de um grande esforço na ciência da computação teórica para des randomizar algoritmos e, finalmente, mostra que P = BPP e resultados de complexidade semelhantes se mantêm.

Veja mais na pesquisa de Zeev: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf

Dana Moshkovitz
fonte
Eu não percebi essa conexão antes, obrigado !!
Hsien-Chih Chang,