O derandomizacji wielomianowych testów tożsamości

W teście tożsamości wielomianowej szukamy algorytmu deterministycznego, aby wnioskować o równości dwóch wielomianów . Ważnym otwartym problemem jest derandomizacja znanych skutecznych algorytmów randomizowanych i wytwarzanie wydajnego algorytmu deterministycznego. Czy istnieje kompletny problem dla PIT, tak że derandomizacja testów tożsamości dla tej jednej klasy wielomianów rozwiązuje ten otwarty problem? Jeśli nie, to czy istnieją klasy wielomianów, w których problem został rozwiązany, i klasy, w których są one otwarte?$g,h\in\Bbb Z[x_1,\dots,x_n]$

[tl;dr] Wiele wiadomo i jest to bardzo aktywny obszar! [/tl;dr]

Ważne jest, aby określić reprezentację wejściowych wielomianów, ponieważ są one podawane jako listy współczynników lub niezerowe jednomianów, problem jest trywialny. Dlatego zwykle zakłada się, że wielomiany są podawane jako obwody arytmetyczne (inaczej programy proste). Ogólny przypadek sprowadza się do sprawdzenia, czy dany wielomian jest wielomianem zerowym.

Przeanalizowano dwa główne ustawienia: skrzynkę Whitebox, w której jeden ma obwód arytmetyczny i można go sprawdzić, oraz skrzynkę Blackbox, w której wiadomo pewne rzeczy o obwodzie (rozmiar, stopień formalny ...), ale nie można sprawdź to, oceń tylko niektóre wartości.

Oto niektóre z ograniczeń badanych obwodów:

• $2$$3$$4$$3$$4$
• Wachlowanie u góry / u dołu: W przypadku obwodów o ograniczonej głębokości udowodniono wiele wyników, gdy wachlowanie (lub prąd, czyli liczba wejść do danej bramki) albo górnej lub dolnej bramki jest ograniczone.
• Przebadano również inne ograniczenia, takie jak ograniczenie liczby przypadków użycia zmiennej.

To badanie przez Nitin Saxena jest źródłem dobra dla tych wyników. Zauważ jednak, że ma on już ponad rok (!), I jest to bardzo aktywny obszar. Więc najnowsze wyniki nie są objęte gwarancją.

Wreszcie istnieją powiązania między derandomizacją PIT a derandomizacją innych problemów:

• Lemma normalizacyjna Noether , autor: Ketan D. Mulmuley;
• Wieloczynnikowa faktoryzacja wielomianowa , autor: Swastik Kopparty, Shubhangi Saraf i Amir Shpilka.