Überprüfen, ob ein Polynom in lineare Faktoren zerfällt

9

Sei ein Polynom, das durch eine arithmetische Schaltung der Größe . Gibt es bei als Eingabe einen deterministischen Algorithmus, um zu überprüfen, ob alle irreduziblen Faktoren von in lineare Formen sind? In einer verwandten Anmerkung können wir bei einer linearen Form deterministisch prüfen, ob Faktor . Natürlich möchten wir, dass die Laufzeit in beiden Fällen polynomisch ist. Mit Größe meinen wir die Gesamtbitgröße. Es kann auch angenommen werden, dass der Grad von in polynomisch istfQ[x1,x2,,xn]CsCfQ[x1,x2,,xn]l=i=1nlixilffn.

Gorav Jindal
quelle
Wenn Sie "Größe " sagen , bedeutet dies die Anzahl der Gates / Drähte oder die Gesamtbitgröße (unter Berücksichtigung der Bits, die zur Beschreibung von Konstanten in der Schaltung verwendet werden)? s
Joshua Grochow
@JoshuaGrochow, ja Größe ist die Gesamtbitgröße hier.
Gorav Jindal
2
Drei Kommentare, die Sie wahrscheinlich bereits im Sinn haben, aber nur für den Fall: 1. In Bezug auf die Polynomzeit sind Faktorisierungsalgorithmen für arithmetische Schaltungen in der Größe und dem Grad des Polynoms polynomisch, und mir sind keine Algorithmen für verwandte Aufgaben bekannt, die ausgeführt werden Zeitpolynom nur in der Größe. 2. In Bezug auf den Determinismus sind diese Algorithmen randomisiert und deterministische Varianten werden in der Anzahl der Variablen exponentiell. 3. Die zweite Frage kann in ein PIT-Problem übersetzt werden, sodass Ihre Frage einen bestimmten PIT-Algorithmus derandomisiert.
Bruno
Ich füge hinzu, dass ich diese Probleme sehr interessant finde und ich würde gerne wissen, was dazu bereits bekannt ist!
Bruno
Zu PIT, Polynomidentitätstests über Schwartz-Zippel / Wikipedia & es gibt viel aktive Forschung in diesem Bereich. (Zu diesem Punkt kann PIT verwendet werden, um ganze Zahlen zu
faktorisieren,

Antworten:

8

Soweit ich weiß, ist der beste Algorithmus, den wir derzeit prüfen müssen, ob (gegeben durch eine arithmetische Schaltung) in lineare Faktoren zerlegt werden kann, der randomisierte Algorithmus von Kaltofen (PDF), der tatsächlich Blackboxen für alle irreduziblen Faktoren von und arbeitet über ein ausreichend großes Feld. Tatsächlich wurde kürzlich von Kopparty, Saraf und Shpilka gezeigt, dass dieses Problem der Polynomfaktorisierung für allgemeine Schaltungen dem Problem der Blackbox-PIT für allgemeine Schaltungen entspricht.ff

Wie von Bruno erwähnt, reduziert sich dies auf ein bestimmtes PIT-Problem , wenn Sie daran interessiert sind, zu überprüfen, ob die gegebene Schaltung durch eine gegebene teilbar ist . Wir wissen im Allgemeinen nicht, wie man das deterministisch macht, aber ich kenne einen Sonderfall, in dem wir wissen, wie man diese PIT macht. Es gibt einen deterministischen Polyzeitalgorithmus (PDF) , um zu überprüfen, ob eine gegebene ein gegebenes spärliches Polynom teilt .f

(Ein weiterer trivialer Sonderfall, wenn durch eine begrenzte Schaltung mit oberer Fan-In-Tiefe drei gegeben ist. Dort ist auch eine begrenzte Schaltung mit Fan-Tiefe drei, und wir wissen, wie man PIT in deterministischer Polynomzeit macht.)ffmod

Ramprasad
quelle