Полиномиальный метод для результатов сложности

29

Полиномиальные методы , скажем, теорема о комбинаторном нульстелленсаце и Шевалле – Предупреждениее, являются мощными инструментами аддитивной комбинаторики. Представляя проблему с собственными полиномами, они могут гарантировать существование решения или количество решений полиномов. Они использовались для решения таких задач, как ограниченные наборы сумм или задачи с нулевой суммой , и некоторые из теорем в этой области могут быть доказаны только такими методами.

Для меня неконструктивная манера использования этих методов действительно удивительна, и мне интересно, как мы можем применять эти методы для доказательства любых интересных включений и разделений классов сложности (даже если результат может быть решен другими методами).

Известны ли какие-либо результаты сложности, которые можно доказать полиномиальными методами?

Сянь-Чжи Чан 張顯 之
источник

Ответы:

29

Некоторые классические примеры использования полиномиального метода:

Кроме того, анализ Фурье булевых функций ( это отличный курс Райана О'Доннелла ) имеет ОГРОМНУЮ коллекцию потрясающих результатов, моим любимым является доказательство теоремы Гольдрайха-Левина по Кушилевицу-Мансур-Нисану .

Скотт Ааронсон фактически дал учебное пособие на FOCS'08 по теме « Полиномиальный метод в классических и квантовых вычислениях (ppt) ».

Надеюсь это поможет.

Ramprasad
источник
Вау ... так много потрясающих результатов !! Это действительно потрясающе, большое спасибо!
Сянь-Чи Чанг 之 之
20

Есть результат Зеев Двира о конечной полевой задаче Какейи, который упоминался ранее на этом сайте. Зеев использовал полиномиальный метод, чтобы понизить число точек в любом наборе точек в F ^ n (конечное поле F, натуральное число n), которое содержит линию в каждом направлении. Этот результат фактически привлек внимание людей в анализе к полиномиальному методу.

Результат Зеева был мотивирован задачей построения экстракторов случайности . Это является частью огромных усилий теоретической информатики по дерандомизации алгоритмов и в конечном итоге показывает, что P = BPP и аналогичные результаты сложности имеют место.

Подробнее об этом можно узнать в обзоре Зеева: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf.

Дана Мошковиц
источник
Я не заметил эту связь раньше, спасибо!
Сянь-Чи Чанг 之 之