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?
fuente
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
fuente