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?
źródło
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
źródło