Sprawdzanie, czy wielomian wpływa na czynniki liniowe

Niech będzie wielomianem podanym przez obwód arytmetyczny o rozmiarze . Biorąc pod uwagę jako dane wejściowe, czy istnieje algorytm deterministyczny, aby sprawdzić, czy wszystkie nieredukowalne czynniki w są formami liniowymi? W pokrewnej uwadze, biorąc pod uwagę postać liniową , możemy sprawdzić deterministycznie, czy jest współczynnikiem . Oczywiście chcemy, aby czas działania był w obu przypadkach wielomianowy. Przez rozmiar rozumiemy całkowity rozmiar bitu. Można również założyć, że stopień jest wielomianem w $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ $C$ $s$ $C$ $f$ $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$ $l$ $f$ $f$ $n$ .

ds.algorithms algebraic-complexity arithmetic-circuits

— Gorav Jindal
źródło

Kiedy mówisz „rozmiar ”, czy to oznacza liczbę bramek / drutów, czy całkowity rozmiar bitów (biorąc pod uwagę bity użyte do opisania jakichkolwiek stałych w obwodzie)?

s

$s$

— Joshua Grochow

@JoshuaGrochow, tak, rozmiar jest tutaj bitem.

— Gorav Jindal

Trzy komentarze, które prawdopodobnie już masz na myśli, ale na wszelki wypadek: 1. Jeśli chodzi o czas wielomianowy, algorytmy faktoryzacji dla obwodów arytmetycznych są wielomianowe pod względem wielkości i stopnia wielomianu, i nie znam algorytmów dla powiązanych zadań, które działają w wielomian czasowy tylko w rozmiarze. 2. Jeśli chodzi o determinizm, algorytmy te są randomizowane, a warianty deterministyczne stają się wykładnicze pod względem liczby zmiennych. 3. Drugie pytanie można przełożyć na problem PIT, więc twoje pytanie sprowadza się do derandomizacji określonego algorytmu PIT.

— Bruno,

Dodam również, że uważam te problemy za bardzo interesujące i chciałbym wiedzieć, co już na ten temat wiadomo!

— Bruno

ponownie PIT, testowanie tożsamości wielomianowej za pośrednictwem Schwartz – Zippel / wikipedia i istnieje wiele aktywnych badań w tej dziedzinie. (ponownie, że pg PIT może być użyty do uwzględnienia liczb całkowitych, ale co to jest referencja, która opisuje, jak używać go do uwzględniania wielomianów?)

— vzn

O ile mi wiadomo, najlepszy algorytm, który musimy obecnie sprawdzić, czy $f$ (dane przez obwód arytmetyczny) można podzielić na czynniki liniowe za pomocą losowego algorytmu Kaltofen (PDF), który faktycznie wytwarza czarne skrzynki dla wszystkich nieredukowalnych czynników $f$ i działa na każdym wystarczająco dużym polu. W rzeczywistości ten problem faktoryzacji wielomianowej dla obwodów ogólnych został ostatnio wykazany przez Kopparty, Sarafa i Szpilkę jako równoważny problemowi blackbox-PIT dla obwodów ogólnych.

Jak wspomniał Bruno, jeśli chcesz sprawdzić, czy dany obwód jest podzielny przez dany $\ell$ , to redukuje się do konkretnego problemu PIT. Ogólnie nie wiemy, jak to zrobić deterministycznie, ale znam jeden szczególny przypadek, w którym wiemy, jak zrobić ten PIT. Istnieje deterministyczny algorytm wieloczasowy (PDF), aby sprawdzić, czy dany $\ell$ dzieli dany rzadki wielomian $f$ .

(Kolejny trywialny specjalny przypadek, kiedy $f$ jest podawany przez ograniczony obwód z trzema głębokościami wentylatora. Tam, $f \bmod \ell$ jest również ograniczonym do trzech obwodów wachlarzem i wiemy, jak wykonać PIT w deterministycznym czasie wielomianowym.)

— Ramprasad
źródło