Класс сложности этой проблемы?

Я пытаюсь понять, к какому классу сложности относится следующая проблема:

Экспонирующая полиномиальная корневая проблема (EPRP)

Пусть - многочлен с deg ( p ) ≥ 0 с коэффициентами, взятыми из конечного поля G F ( q ), где q - простое число, а r - примитивный корень для этого поля. Определите решения: p ( x ) = r x (или, что эквивалентно, нули p ( x ) - r x ), где r x означает возведение в степень r .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Обратите внимание, что когда (многочлен является константой), эта проблема возвращается к проблеме дискретного логарифма, которая считается NP-промежуточной, то есть она находится в NP, но не в P и не NP-полной.$\deg(p)=0$

Насколько мне известно, эффективных (полиномиальных) алгоритмов для решения этой проблемы не существует (алгоритмы Берлекампа и Кантора-Цассенхауза требуют экспоненциального времени). Найти корни такого уравнения можно двумя способами:

• Попробуйте все возможные элементы в поле и проверьте, удовлетворяют ли они уравнению или нет. Ясно, что это требует экспоненциального времени в размерах модуля поля;$x$

• Экспонента может быть переписана в полиномиальной форме, используя интерполяцию Лагранжа для интерполяции точек { ( 0 , r 0 ) , ( 1 , r 1 ) , … , ( q - 1 , r q - 1 ) } , определяя многочлен f ( x ) . Этот полином идентичен с г й именно потому , что мы работаем над конечным полем. Тогда разница $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ , может быть учтено, чтобы найти корни данного уравнения (используя алгоритмы Берлекампа или Кантора – Цассенхауза), и корни считывают факторы. Однако этот подход даже хуже, чем полный поиск: поскольку в среднем полином, проходящий по n заданным точкам, будет иметь n ненулевых коэффициентов, даже только для ввода в интерполяцию Лагранжа потребуется экспоненциальное пространство в битовом размере поля.$p(x) - f(x)$$n$$n$

Кто-нибудь знает, считается ли эта проблема также NP-промежуточной или относится к какому-либо другому классу сложности? Ссылка будет принята с благодарностью. Благодарю.

приму ответ на этот вопрос. в этом вопросе нет ссылок, но ему дается аббревиатура "EPRP", как если бы ее изучали несколько человек. Кто-нибудь знает, так ли это? MC спрашивающего, кажется, имеет значительную массу в этой области, но это помогло бы значительно перечислить некоторые "близлежащие" ссылки, известные / проверенные, чтобы понять, почему у них есть некоторый пробел, который (?) не покрывает этот предположительно особый случай.

Обычно это помогает найти «ближайшие доступные ссылки» и определить, как проблема отличается или похожа. Здесь приводится всеобъемлющая ссылка, которая, кажется, рассматривает тесно связанные проблемы. Подумайте, что спрашивающий MC должен попытаться найти ближайший случай проблемы в этой ссылке, или, может быть, какой-то другой, а затем указать, как этот вопрос конкретно отличается от общих проблемных случаев, приведенных в ссылке. ссылка имеет длинный список связанных ссылок, чтобы также проверить наличие ближайших / связанных проблем. он рассматривает сложность проблемы и дает эффективные алгоритмы P-времени для различных случаев.

О РЕШЕНИИ УНИВЕРНЫХ ПОЛИНОМИЧЕСКИХ УРАВНЕНИЙ НА КОНЕЧНЫХ ПОЛЯХ И НЕКОТОРЫХ СООТВЕТСТВУЮЩИХ ПРОБЛЕМАХ Цзы Во Сзе, доктор философских наук, 2007

... мы представляем детерминированный полиномиальный алгоритм для решения полиномиальных уравнений над некоторыми семействами конечных полей. Обратите внимание, что полиномиальные уравнения являются мощными конструкциями. Многие проблемы могут быть сформулированы как полиномиальные уравнения.