Método polinómico para resultados complejos.

29

Los métodos polinómicos , por ejemplo, el teorema combinatorio de Nullstellensatz y Chevalley-Warning son herramientas poderosas en la combinatoria aditiva. Al representar un problema con los polinomios adecuados, pueden garantizar la existencia de una solución o el número de soluciones para los polinomios. Se han utilizado para resolver problemas como sumas restringidas o problemas de suma cero , y algunos de los teoremas en esta área solo pueden demostrarse mediante tales métodos.

Para mí, la forma no constructiva de estos métodos es realmente sorprendente, y tengo curiosidad acerca de cómo podemos aplicar estos métodos para probar cualquier inclusión o separación interesante de las clases de complejidad (incluso si el resultado se puede resolver con otros métodos).

¿Se conocen resultados de complejidad que se puedan probar mediante métodos polinómicos?

Hsien-Chih Chang 張顯 之
fuente

Respuestas:

29

Algunos ejemplos clásicos del uso del método polinomial son:

Además, el análisis de Fourier de las funciones booleanas ( aquí hay un gran curso de Ryan O'Donnell ) tiene una ENORME colección de resultados asombrosos, mi favorito es la prueba de Kushilevitz-Mansour-Nisan del teorema de Goldreich-Levin .

Scott Aaronson había dado un tutorial en FOCS'08 sobre " El método polinómico en computación clásica y cuántica (ppt) ".

Espero que esto ayude.

Ramprasad
fuente
Wow ... ¡tantos resultados increíbles! Estos son realmente increíbles, ¡muchas gracias!
Hsien-Chih Chang 張顯 之
20

Existe el resultado de Zeev Dvir en el problema de Kakeya de campo finito que se mencionó anteriormente en este sitio web. Zeev usó el método polinomial para limitar el número de puntos en cualquier conjunto de puntos en F ^ n (campo finito F, n número natural) que contiene una línea en cada dirección. Este resultado realmente llamó la atención de las personas en análisis sobre el método polinómico.

El resultado de Zeev fue motivado por la tarea de construir extractores de aleatoriedad . Esto es parte de un gran esfuerzo en la informática teórica para desrandomizar algoritmos y, en última instancia, muestra que P = BPP y resultados de complejidad similares se mantienen.

Ver más en la encuesta de Zeev: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf

Dana Moshkovitz
fuente
No noté esta conexión antes, ¡gracias!
Hsien-Chih Chang 張顯 之