Полиномиальные методы , скажем, теорема о комбинаторном нульстелленсаце и Шевалле – Предупреждениее, являются мощными инструментами аддитивной комбинаторики. Представляя проблему с собственными полиномами, они могут гарантировать существование решения или количество решений полиномов. Они использовались для решения таких задач, как ограниченные наборы сумм или задачи с нулевой суммой , и некоторые из теорем в этой области могут быть доказаны только такими методами.
Для меня неконструктивная манера использования этих методов действительно удивительна, и мне интересно, как мы можем применять эти методы для доказательства любых интересных включений и разделений классов сложности (даже если результат может быть решен другими методами).
Известны ли какие-либо результаты сложности, которые можно доказать полиномиальными методами?
источник
Есть результат Зеев Двира о конечной полевой задаче Какейи, который упоминался ранее на этом сайте. Зеев использовал полиномиальный метод, чтобы понизить число точек в любом наборе точек в F ^ n (конечное поле F, натуральное число n), которое содержит линию в каждом направлении. Этот результат фактически привлек внимание людей в анализе к полиномиальному методу.
Результат Зеева был мотивирован задачей построения экстракторов случайности . Это является частью огромных усилий теоретической информатики по дерандомизации алгоритмов и в конечном итоге показывает, что P = BPP и аналогичные результаты сложности имеют место.
Подробнее об этом можно узнать в обзоре Зеева: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf.
источник