Klasa złożoności tego problemu?

12

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)0GF(q)qr

p(x)=rx
p(x)rxrxr

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 prx{(0,r0),(1,r1),,(q1,rq1)}f(x)rx , 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)nn

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.

Massimo Cafaro
źródło
1
Przepraszam, miałem na myśli, że uważa się za NP-średniozaawansowany. Edytuję pytanie, aby to odzwierciedlić.
Massimo Cafaro,
1
p(x)=rxp(x)rxp(x)f(x)f(x)
1
Czy logarytm dyskretny nie jest tego szczególnym przypadkiem? Jest więc co najmniej tak trudny jak dyskretny rdzeń i oczywiście w NP. Jeśli uważasz, że dyskretny dziennik to NPI, to ten również jest. Możesz zapytać, czy istnieje jakiś wydajny algorytm kwantowy dla tego problemu.
Kaveh
2
@Kaveh: W pytaniu wspomniano, że dyskretny dziennik jest szczególnym przypadkiem. Ten problem może być trudniejszy (NP-zupełny), choć sądzę, że są takie same. Ale masz rację, że poszukiwanie algorytmów wielomianowych jest dość beznadziejne.
domotorp
1
crossposted: mathoverflow.net/questions/154721/…
domotorp

Odpowiedzi:

-5

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.

vzn
źródło
2
ta „odpowiedź” powinna być komentarzem z linkiem do pracy magisterskiej.
Sasho Nikolov
1
@vzn, główne algorytmy (interpolacja berlekamp, ​​Cantor-Zassenhaus i Lagrange) zostały zacytowane w moim pytaniu i można łatwo znaleźć mnóstwo powiązanych materiałów przeszukujących sieć. Mógłbym nawet dodać tutaj algorytm Shoup, ale nie jestem w stanie dodać żadnego pojedynczego odwołania, w którym zbadano ten problem. Skrót „EPRP” to tylko sposób na odniesienie się do problemu, którego nie znajdziesz w literaturze. W każdym razie sprawdziłem referencje, które uprzejmie podałeś, ale przeanalizowane problemy są zbyt łatwe i oparte na uproszczeniu założeń, które niestety nie mają zastosowania w moim przypadku.
Massimo Cafaro
1
Również problemy badane w doktoracie. tezy nie są „ogólne”: są to konkretne problemy, z uproszczonymi założeniami, które czynią je wykonalnymi. Bardzo interesująca i solidna praca, ale gdyby dr Tsz Wo Sze rozwiązał EPRP za pomocą algorytmu wielomianowego, prawdopodobnie do tej pory otrzymałby medal Fieldsa ;-)
Massimo Cafaro
2
xϕ(ϕ(q))
3
@VZN: hej stary, dlaczego ciągle trollujesz tę stronę? To musi być żart. Jesteś oczywiście informatykiem (nawet nie używasz swojej prawdziwej tożsamości, tak jak inni prawdziwi naukowcy tutaj, tacy jak Shor i Growchow, itp.
William Hird,