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$.

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.)