Klasa złożoności tego problemu?

Próbuję zrozumieć, do której klasy złożoności należy następujący problem:

Wykładniczy wielomianowy problem z korzeniem (EPRP)

Niech będzie wielomianem o deg ( p ) ≥ 0 ze współczynnikami wyciągniętymi z pola skończonego G F ( q ) z q liczbą pierwszą, a r pierwotnym pierwiastkiem dla tego pola. Określ rozwiązania: p ( x ) = r x (lub równoważnie zer p ( x ) - r x ), gdzie r x oznacza wykładnik r .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Zauważ, że gdy (wielomian jest stały), problem ten powraca do problemu dyskretnego logarytmu, który uważa się za NP-średniozaawansowany, tj. Nie ma w NP, ale ani w P, ani w NP-zupełny.$\deg(p)=0$

Według mojej najlepszej wiedzy nie istnieją wydajne (wielomianowe) algorytmy do rozwiązania tego problemu (algorytmy Berlekamp i Cantor – Zassenhaus wymagają czasu wykładniczego). Znalezienie pierwiastków do takiego równania można wykonać na dwa sposoby:

• Wypróbuj wszystkie możliwe elementy polu i sprawdź, czy spełniają one równanie, czy nie. Oczywiście wymaga to czasu wykładniczego w bitach modułu pola;$x$

• Wykładniczy może być przepisana w formie wielomianów, stosując interpolację Lagrange'a interpolacji punktów { ( 0 , R 0 ) , ( 1 , R 1 ) , ... , ( P - 1 , R P - 1 ) } , wyznaczanie wielomian f ( x ) . Wielomian ten jest identyczny do r x właśnie dlatego, że pracują na polu skończonych. Następnie różnica $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ , można rozłożyć na czynniki faktyczne w celu znalezienia pierwiastków danego równania (za pomocą algorytmów Berlekamp lub Cantor – Zassenhaus) i pierwiastków odczytanych z czynników. Jednak to podejście jest nawet gorsze niż wyszukiwanie wyczerpujące: ponieważ średnio wielomian przechodzący przez n danych punktów będzie miał n -zerowych współczynników, nawet tylko dane wejściowe do interpolacji Lagrange'a będą wymagały przestrzeni wykładniczej w rozmiarze bitu pola.$p(x) - f(x)$$n$$n$

Czy ktoś wie, czy uważa się, że ten problem ma również charakter pośredni NP, czy też należy do innej klasy złożoności? Referencja będzie bardzo mile widziana. Dzięki.

zrobi pchnięcie nożem w odpowiedzi na to. w pytaniu nie ma żadnych odnośników, ale jest oznaczony akronimem „EPRP”, tak jakby studiowało go więcej niż jedna osoba. czy ktoś wie, czy tak jest? pytający MC wydaje się mieć znaczące bkg w tym obszarze, ale znacznie pomogłoby wymienić niektóre „pobliskie” referencje znane / sprawdzone, aby zrozumieć, dlaczego mają jakąś lukę, która nie obejmuje (?) tego rzekomo szczególnego przypadku.

zwykle pomaga znaleźć „najbliższe dostępne referencje” i ustalić, w jaki sposób problem jest inny lub podobny. tutaj jest obszerna referencja, która wydaje się brać pod uwagę ściśle powiązany problem (problemy). pomyśl, że pytający MC powinien spróbować zlokalizować najbliższy przypadek problemu w tej informacji, a może jakiś inny, a następnie wskazać, w jaki sposób ta sprawa jest wyraźnie odmienna od ogólnych spraw problemowych podanych w referencji. sędzia ma długą listę powiązanych sędziów, aby również sprawdzić pobliskie / powiązane problemy. rozważa złożoność problemu i podaje wydajne algorytmy czasu P dla różnych przypadków.

O ROZWIĄZANIU UNIWERSALNYCH RÓWNOLEGŁOŚCI NA NIESKOŃCZONYCH DZIEDZINACH I NIEKTÓRYCH ZWIĄZANYCH PROBLEMACH Tsz Wo Sze, doktor filozofii, 2007

... przedstawiamy deterministyczny algorytm wielomianowy w czasie do rozwiązywania równań wielomianowych w niektórych rodzinach pól skończonych. Zauważ, że równania wielomianowe są potężnymi konstrukcjami. Wiele problemów można sformułować jako równania wielomianowe.