Komplexitätsklasse dieses Problems?

Ich versuche zu verstehen, zu welcher Komplexitätsklasse das folgende Problem gehört:

Exponentiating Polynomial Root Problem (EPRP)

Sei ein Polynom mit deg ( p ) ≥ 0 mit Koeffizienten, die aus einem endlichen Feld G F ( q ) mit q einer Primzahl gezogen werden, und r eine Grundwurzel für dieses Feld. Bestimmen Sie die Lösungen von: p ( x ) = r x (oder äquivalent die Nullen von p ( x ) - r x ), wobei r x die Exponentiierung von r bedeutet .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Beachten Sie, dass bei $\deg(p)=0$ (das Polynom ist eine Konstante), kehrt dieses Problem zum Diskreten Logarithmus-Problem zurück, von dem angenommen wird, dass es NP-Intermediat ist, dh es ist in NP, aber weder in P noch in NP-vollständig.

Es gibt meines Wissens keine effizienten (polynomiellen) Algorithmen zur Lösung dieses Problems (Berlekamp- und Cantor-Zassenhaus-Algorithmen benötigen exponentielle Zeit). Das Finden von Wurzeln für eine solche Gleichung kann auf zwei Arten erfolgen:

• Probieren Sie alle möglichen Elemente im Feld aus und prüfen Sie, ob sie der Gleichung entsprechen oder nicht. Dies erfordert eindeutig eine exponentielle Zeit in der Bitgröße des Feldmoduls;$x$

• Das Exponential kann in Polynomform umgeschrieben werden, indem die Punkte { ( 0 , r 0 ) , ( 1 , r 1 ) , … , ( q - 1 , r q - 1 ) } mit Lagrange-Interpolation interpoliert werden , wobei a bestimmt wird Polynom f ( x ) . Dieses Polynom ist genau deshalb mit r x identisch , weil wir an einem endlichen Feld arbeiten. Dann ist der Unterschied $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ kann berücksichtigt werden, um die Wurzeln der gegebenen Gleichung (unter Verwendung von Berlekamp- oder Cantor-Zassenhaus-Algorithmen) zu finden, und die Wurzeln können die Faktoren ablesen. Dieser Ansatz ist jedoch noch schlimmer als eine erschöpfende Suche: Da ein Polynom, das an n gegebenen Punktenvorbeigeht, im Durchschnitt n Nicht-Null-Koeffizienten aufweist, erfordert selbst die Eingabe in die Lagrange-Interpolation exponentiellen Raum in der Feldbitgröße.$p(x) - f(x)$$n$$n$

Weiß jemand, ob man glaubt, dass dieses Problem auch NP-intermediär ist oder zu einer anderen Komplexitätsklasse gehört? Eine Referenz wird sehr geschätzt. Vielen Dank.

Ich werde versuchen, darauf zu antworten. In der Frage sind keine Referenzen angegeben, aber es wird ein Akronym "EPRP" vergeben, als ob mehr als eine Person es studiert hätte. Weiß jemand, ob das der Fall ist? Der Fragesteller MC scheint in diesem Bereich ein erhebliches Gewicht zu haben, aber es würde erheblich dazu beitragen, einige "in der Nähe" befindliche Refs aufzulisten, die bekannt sind / überprüft wurden, um zu verstehen, warum sie eine Lücke haben, die diesen vermeintlichen Sonderfall nicht (?) abdeckt.

In der Regel hilft es, "nächstgelegene verfügbare Referenzen" zu finden und festzustellen, ob das Problem unterschiedlich oder ähnlich ist. Hier ist ein umfassender Verweis, der nah verwandte Probleme zu berücksichtigen scheint. Denken Sie, dass der Fragesteller MC versuchen sollte, den nächstgelegenen Fall des Problems in dieser Referenz oder vielleicht einen anderen zu lokalisieren, und weisen Sie dann darauf hin, dass sich dieser angefragte Fall spezifisch von den in der Referenz angegebenen allgemeinen Problemfällen unterscheidet. der ref hat eine lange liste verwandter refs, um auch nach nahegelegenen / verwandten problemen zu suchen. Er betrachtet die Komplexität des Problems und gibt effiziente P-Zeit-Algorithmen für verschiedene Fälle an.

ZUR LÖSUNG UNIVARIATER POLYNOMGLEICHUNGEN ÜBER ENDFELDER UND EINIGE VERWANDTE PROBLEME Tsz Wo Sze, Doktor der Philosophie, 2007

... präsentieren wir einen deterministischen Polynom-Zeit-Algorithmus zur Lösung von Polynomgleichungen über einige Familien endlicher Felder. Beachten Sie, dass Polynomgleichungen mächtige Konstrukte sind. Viele Probleme können als Polynomgleichungen formuliert werden.