Komplexität der Matrixversorgung

Sei eine quadratische Ganzzahlmatrix und sei eine positive Ganzzahl. Ich interessiere mich für die Komplexität des folgenden Entscheidungsproblems: $M$ $n$

Ist der obere rechte Eintrag von positiv? $M^n$

Beachten Sie, dass der offensichtliche Ansatz des iterierten Quadrierens (oder einer anderen expliziten Berechnung) es erforderlich macht, dass wir potenziell Ganzzahlen mit doppelt exponentieller Größe behandeln, dh mit exponentiell vielen Bits. Es ist jedoch leicht zu erkennen, dass das Problem in der Klasse "PosSLP" von Allender et al. ( "Über die Komplexität der numerischen Analyse", SIAM J. Comput. 38 (5) ) und daher in der vierten Ebene der Zählhierarchie liegt .

1) Ist es möglich, dieses Matrixversorgungsproblem in eine Klasse mit geringerer Komplexität einzuteilen?

2) Wenn nicht, könnte es möglicherweise PosSLP-schwer sein?

3) Ich interessiere mich besonders für das Matrix-Powering-Problem bei niedrigdimensionalen Matrizen, dh bis einschließlich 6x6-Matrizen. Könnte die Komplexität für solche Matrizen geringer sein?

cc.complexity-theory linear-algebra matrices Joel
quelle

Sollte der Titel nicht in "Komplexität der Matrixversorgung" geändert werden? Matrixexponentiation (siehe zB en.wikipedia.org/wiki/Matrix_exponential ) wird allgemein als "A = exp (B)" für Matrizen A, B verstanden.

Martin Schwarz

Ich werde es bearbeiten. Das ist ein guter Punkt, @MartinSchwarz

Suresh Venkat

Wenn Sie die Matrix in die PDP-1-Form transformieren (was für eine kleine Matrix und eine ausreichend hohe Leistung von n als konstant angesehen werden kann), können Sie das Vorzeichen jedes Eintrags der diagonalen Einträge trivial kennen. Dann ist es einfach, die verbleibenden zwei Matrixmultiplikationen herauszufinden.

Robert Mason

@ Robert Mason: Ich bin nicht ganz sicher, was Sie vorschlagen. Wenn D die jordanische kanonische Form von M ist, so dass M ^ n = P ^ (- 1) D ^ n P ist, dann sind die Einträge von D typischerweise komplexe algebraische Zahlen. Was meinen Sie also mit ihrem "Vorzeichen"? Ich bin damit einverstanden, dass Sie D und P in Polynomialzeit berechnen können (unter der Annahme von Standarddarstellungen algebraischer Zahlen), aber der Ausdruck, den Sie für die Eingabe von M ^ n = P ^ (- 1) D ^ n P oben rechts erhalten, wird ein Ausdruck sein Ich verstehe nicht, wie Sie das Vorzeichen dieses Ausdrucks effizient bestimmen können.

Joel

@Robert Mason: Ich verstehe immer noch nicht - wie / warum ist dies für invertierbare Matrizen effizient? (Und im Übrigen sind "die meisten" Matrizen invertierbar und nicht umgekehrt.)

Joel

Komplexität der Matrixversorgung

Antworten: