Kelas kompleksitas masalah ini?

Saya mencoba memahami kelas kompleksitas mana yang termasuk masalah berikut:

Memecahkan Masalah Polinomial Root (EPRP)

Biarkan be polinomial dengan deg ( p ) ≥ 0 dengan koefisien diambil dari bidang yang terbatas G F ( q ) dengan q bilangan prima, dan r akar primitif untuk bidang itu. Tentukan solusi dari: p ( x ) = r x (atau ekuivalen, angka nol dari p ( x ) - r x ) di mana r x sarana exponentiating r .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Perhatikan bahwa, ketika (polinom adalah konstanta), masalah ini kembali ke Masalah Logaritma Diskrit, yang diyakini sebagai NP-Menengah, yaitu di NP tetapi tidak di P atau NP-lengkap.$\deg(p)=0$

Sejauh pengetahuan saya, algoritma (polinomial) yang efisien untuk menyelesaikan masalah ini tidak ada (algoritma Berlekamp dan Cantor-Zassenhaus membutuhkan waktu yang eksponensial). Menemukan akar persamaan tersebut dapat dilakukan dengan dua cara:

• Coba semua item yang mungkin di bidang, dan periksa apakah mereka memenuhi persamaan atau tidak. Jelas, ini membutuhkan waktu eksponensial dalam bitsize modulus bidang;$x$

• Eksponensial dapat ditulis dalam bentuk polinomial, dengan menggunakan Lagrange interpolasi untuk interpolasi titik-titik { ( 0 , r 0 ) , ( 1 , r 1 ) , ... , ( q - 1 , r q - 1 ) } , menentukan polinomial f ( x ) . Polinomial ini identik dengan r x justru karena kita bekerja pada bidang yang terbatas. Kemudian, perbedaannya $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ , dapat diperhitungkan untuk menemukan akar dari persamaan yang diberikan (menggunakan algoritma Berlekamp atau Cantor-Zassenhaus) dan akar membaca faktor-faktor. Namun, pendekatan ini bahkan lebih buruk daripada pencarian lengkap: karena, rata-rata, melewati polinomial oleh n poin yang diberikan akan memilikikoefisien n -nol, bahkan hanya input untuk interpolasi Lagrange akan membutuhkan ruang eksponensial dalam ukuran bit bidang.$p(x) - f(x)$$n$$n$

Apakah ada yang tahu jika masalah ini diyakini sebagai NP-intermediate juga atau milik kelas kompleksitas lainnya? Referensi akan sangat dihargai. Terima kasih.

akan mencoba menjawab ini. tidak ada referensi yang diberikan dalam pertanyaan tetapi diberikan akronim "EPRP" seolah-olah lebih dari satu orang telah mempelajarinya. apakah ada yang tahu kalau itu masalahnya? penanya MC tampaknya memiliki bkg yang signifikan di bidang ini tetapi akan sangat membantu untuk mendaftar beberapa referensi "terdekat" yang diketahui / ditinjau untuk memahami mengapa mereka memiliki beberapa celah yang tidak (?) membahas kasus yang seharusnya khusus ini.

biasanya membantu untuk menemukan "referensi terdekat yang tersedia" dan menentukan bagaimana masalahnya berbeda atau serupa. di sini adalah referensi komprehensif yang tampaknya mempertimbangkan masalah yang terkait erat. berpikir bahwa penanya MC harus mencoba menemukan kasus terdekat dari masalah dalam referensi ini, atau mungkin yang lain, dan kemudian menunjukkan bagaimana kasus ini ditanyakan secara khusus berbeda dari kasus-kasus masalah umum yang diberikan dalam referensi. wasit memiliki daftar panjang referensi terkait untuk juga memeriksa masalah terdekat / terkait. dia mempertimbangkan kompleksitas masalah dan memberikan algoritma P-time yang efisien untuk berbagai kasus.

TENTANG MEMENUHI PERSAMAAN POLINOMIAL UNIVARIAT OLEH BIDANG HINGGA DAN BEBERAPA MASALAH TERKAIT Tsz Wo Sze, Doctor of Philosophy, 2007

... kami menyajikan algoritma waktu polinomial deterministik untuk menyelesaikan persamaan polinomial atas beberapa keluarga bidang terbatas. Perhatikan bahwa persamaan polinomial adalah konstruksi yang kuat. Banyak masalah dapat dirumuskan sebagai persamaan polinomial.