Löst man Gleichungssysteme modulo

19

Ich interessiere mich für die Komplexität der Lösung linearer Gleichungen modulo k für willkürliches k (und mit besonderem Interesse für Primkräfte), insbesondere:

Problem. Gibt es für ein gegebenes System von linearen Gleichungen in n Unbekannten modulo k irgendwelche Lösungen?mnk

In der Zusammenfassung zu ihrer Arbeit Struktur und Bedeutung von logspace-MOD-Klassen für die Klassen Mod k L , Buntrock, Damm, Hertrampf und Meinel wird behauptet, dass sie " ihre Bedeutung beweisen, indem sie alle Standardprobleme der linearen Algebra über die endlichen Ringe beweisen / k Z sind für diese Klassen vollständigZ/kZ ". Bei näherer Betrachtung ist die Geschichte komplizierter. Zum Beispiel haben Buntrock et al. zeigen (durch eine Beweisskizze in einem früheren und frei zugänglichen Entwurf von Kaveh, danke!), dass das Lösen linearer Gleichungssysteme stattdessen in der komplementären Klasse coMod k L , zk prime. Es ist nicht bekannt, dass diese Klasse für k composite gleich Mod k L ist , aber das macht mir nichts aus - ich mache mir Sorgen darüber, dass sie keine Anmerkungen dazu machen, ob das Lösen von linearen Gleichungssystemen mod k überhaupt enthalten ist in coMod k L für k Composite!

Frage: Sind in coMod k L Lösungssysteme linearer Gleichungen modulo k für alle positiven k enthalten?

Wenn Sie Gleichungssysteme mit einer höheren Potenz q einer Primzahl p modulo lösen können, können Sie sie auch mit modulo p lösen ; Das Lösen von Gleichungssystemen modulo q ist also coMod p L -hard. Wenn Sie zeigen könnten, dass dieses Problem in Mod q L vorliegt , würden Sie am Ende Mod k L  =  coMod k L für alle k anzeigen . Das ist wahrscheinlich schwer zu beweisen. Aber ist es in coMod k L ?

Niel de Beaudrap
quelle
citeseerx link zum entwurf des papiers . ps: Ein robusterer Weg, mit ist wobei die Menge der akzeptierten Erinnerungen . Es gibt auch eine verwandte Frage in Bezug auf die Beweiskomplexität, vgl. " Die Beweiskomplexität der linearen Algebra " von Soltys und Cook, APAL 2004.modkmodkAA[k1]modk
Kaveh
2
was ist mit nur k = 4 und Parität-L?
Domotorp

Antworten:

9

Ich bin froh zu sagen, dass ich denke, dass wir diese Frage bejahen können: Das heißt, zu entscheiden, ob eine lineare Kongruenz durchführbar ist, modulo k ist coMod k L -complete.

Wir können dieses Problem tatsächlich auf den Sonderfall der Primkräfte reduzieren. Man kann zeigen, dass:

Normalform. Die Klasse coMod k L besteht aus Sprachen L der Form L  =  L p 1  ∩  L p 2  ∩ ...  r L p r  , wobei L p j  ∈  coMod p L und wobei p j über den Primfaktoren von k liegt .

Nach dem Restsatz ergibt jede Lösung eines Gleichungssystems modulo jeder der Primkräfte die k dividieren , eine Lösung desselben Systems, mod k . Wenn das Lösen von Gleichungssystemen über in coMod p L enthalten ist , folgt, dass das Lösen von Gleichungssystemen mod k in coMod k L enthalten ist .pjejpjtj

Es gibt einen Standardalgorithmus, der von McKenzie und Cook beschrieben wurde, um lineare Kongruenzen modulo einer Primzahl zu reduzieren, um eine Spanning-Menge für ihren Nullraum zu konstruieren (nämlich für A x  =  y über einen gegebenen Ring eine Basis für den Nullraum von [ A  |  y zu konstruieren   ] und prüfen Sie, ob es Lösungen mit einem Endkoeffizienten von −1 gibt; und anschließend zum Reduzieren der Konstruktion von Nullraum-Modulo-Primzahlen zur Konstruktion von Nullraum-Modulo-Primzahlen und von Matrixmultiplikations-Modulo-Primzahlen. Die beiden letztgenannten Aufgaben sind Probleme, die für coMod k L machbar sind , vorausgesetzt, Sie können die beteiligten Matrizen konstruieren.

Es zeigt sich, dass die Matrizen, die an der Reduktion von McKenzie und Cook beteiligt sind, selbst durch Matrixmultiplikation und (entscheidend) Division durch einen konstanten Faktor berechnet werden können. Glücklicherweise können für Primleistungen die Koeffizienten der beteiligten Matrizen auf dem Arbeitsband unter Verwendung eines Orakels für coMod p L -Maschinen berechnet werden; und die Division durch eine Konstante kann in NC 1 durchgeführt werden , was wiederum in coMod p L möglich ist . Es stellt sich also heraus, dass das ganze Problem letztendlich in coMod k L umsetzbar ist .

Ausführliche Informationen finden Sie unter [ arxiv: 1202.3949 ].

Niel de Beaudrap
quelle
Ich möchte wissen, ist es Konstante in Ihrer Frage / Antwort? Ich interessiere mich für den Fall, dass die Größe von nicht unbegrenzt ist. kk
Juan Bermejo Vega
1
@ Juan: Ja, ist eine Konstante, obwohl jede Konstante. k
Niel de Beaudrap