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

29

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?

Hsien-Chih Chang 張顯 之
źródło

Odpowiedzi:

29

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

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.

Ramprasad
źródło
Wow ... tak wiele niesamowitych rezultatów !! To są naprawdę niesamowite, dziękuję bardzo !!
Hsien-Chih Chang 之 之
20

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

Dana Moshkovitz
źródło
Nie zauważyłem tego połączenia wcześniej, dzięki !!
Hsien-Chih Chang 之 之