Metoda wielomianowa dla wyników złożoności

Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów. Zostały one wykorzystane do rozwiązania problemów, takich jak ograniczone zestawy sum lub problemy o sumie zerowej , a niektóre twierdzenia w tym obszarze można udowodnić tylko za pomocą takich metod.

Dla mnie niekonstruktywny sposób tych metod jest naprawdę niesamowity i jestem ciekawy, jak możemy zastosować te metody, aby udowodnić wszelkie interesujące inkluzje i separacje klas złożoności (nawet jeśli wynik można rozwiązać innymi metodami).

Czy znane są wyniki złożoności, które można udowodnić metodami wielomianowymi?

Niektóre klasyczne przykłady zastosowania metody wielomianowej to:

• Dowód Razborowa-Smoleńskiego „Parity not in ” ( wiele ekspozycji dostępnych online, tutaj jest jeden )$AC^0$
• Dowód Beigela-Reingolda-Spielmana „PP jest zamknięty pod skrzyżowaniem”
• Wynik Bazzi za oszukiwanie DNF i dowód Bravermana na „ głupców niezależności Polylog$AC^0$ ”

Również analiza Fouriera funkcji boolowskich ( tutaj jest świetny kurs Ryana O'Donnella ) ma OGROMNY zbiór niesamowitych wyników, moim ulubionym jest dowód Kushilevitza-Mansoura-Nisana na twierdzenie Goldreicha-Levina .

Scott Aaronson faktycznie udzielił tutorialu na FOCS'08 na temat „ Metody wielomianowej w obliczeniach klasycznych i kwantowych (ppt) ”.

Mam nadzieję że to pomoże.

Jest wynik Zeev Dvir na problemie Kakeya o skończonym polu, o którym wcześniej wspomniano na tej stronie. Zeev zastosował metodę wielomianową, aby obniżyć granicę liczby punktów w dowolnym zestawie punktów w F ^ n (F skończone pole, n liczba naturalna), który zawiera linię we wszystkich kierunkach. Ten wynik w rzeczywistości zwrócił uwagę osób analizowanych na metodę wielomianową.

Wynik Zeeva był motywowany zadaniem konstruowania ekstraktorów losowości . Jest to część ogromnego wysiłku w informatyce teoretycznej, aby odandomizować algorytmy i ostatecznie wykazać, że P = BPP i podobne wyniki złożoności zachowują się.

Zobacz więcej w ankiecie Zeev: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf