Apakah memecahkan sistem persamaan modulo

Saya tertarik pada kompleksitas penyelesaian persamaan linear modulo k , untuk arbitrary k (dan dengan minat khusus pada kekuatan utama), khususnya:

Masalah. Untuk sistem tertentu $m$ linear persamaan di $n$ tidak diketahui modulo $k$ , jangan terdapat solusi?

Dalam abstrak untuk makalah mereka Struktur dan pentingnya kelas-ruang MOD-MOD pada kelas -kelas Mod _k L , Buntrock, Damm, Hertrampf, dan Meinel mengklaim bahwa mereka " menunjukkan signifikansi mereka dengan membuktikan bahwa semua masalah standar aljabar linier atas cincin berhingga $\mathbb Z/k\mathbb Z$ lengkap untuk kelas ini ". Pada pemeriksaan lebih dekat, ceritanya lebih rumit. Misalnya, Buntrock et al. menunjukkan (dengan sketsa bukti dalam konsep yang sebelumnya dan dapat diakses secara bebas yang ditemukan oleh Kaveh, terima kasih!) bahwa penyelesaian sistem persamaan linear adalah sebaliknya dalam kelas komplementer coMod _k L , untukk prime. Kelas ini tidak diketahui sama dengan Mod _k L untuk k komposit, tetapi tidak peduli bahwa - apa yang saya khawatirkan adalah fakta bahwa mereka tidak membuat pernyataan tentang apakah sistem penyelesaian persamaan linear mod k bahkan terkandung dalam coMod _k L untuk k komposit!

Pertanyaan: Apakah sistem penyelesaian persamaan linear modulo k terkandung dalam coMod _k L untuk semua k positif?

Jika Anda dapat memecahkan sistem persamaan modulo kekuatan yang lebih tinggi q dari prima p , Anda bisa menyelesaikannya modulo p juga; jadi sistem penyelesaian persamaan modulo q adalah coMod _p L -hard. Jika Anda dapat menunjukkan bahwa masalah ini ada di Mod _q L , Anda pada akhirnya akan menampilkan Mod _k L  =  coMod _k L untuk semua k . Itu mungkin sulit dibuktikan. Tetapi apakah itu dalam coMod _k L ?

Saya senang mengatakan bahwa saya pikir kita dapat menjawab pertanyaan ini dalam afirmatif: yaitu, memutuskan apakah kongruensi linier layak modulo k adalah coMod _k L -complete.

Kami benar-benar dapat mengurangi masalah ini ke kasus khusus kekuatan utama. Seseorang mungkin menunjukkan bahwa:

Bentuk normal. Kelas coMod _k L terdiri dari bahasa L dari bentuk L  =  L _{p 1}  ∩  L _{p 2}  ∩ ... ∩  L _{p r}  , di mana L _{p j}  ∈  coMod _{p j}  L dan di mana p _j berkisar pada faktor-faktor utama k .

Oleh Teorema Sisa, setiap solusi untuk sistem persamaan modulo masing-masing kekuatan utama membagikmemunculkan solusi untuk sistem yang sama, modk. Jadi jika memecahkan sistem persamaan linearlebihp t j$p_{\!j}^{e_j}$$p_{\!j}^{t_j}$ terkandung dalamcomod_pj L, berikut bahwa sistem memecahkan persamaan modkterkandung dalamcomod_kL.

Ada algoritma standar, dijelaskan oleh McKenzie dan Cook untuk mengurangi kongruensi linier modulo kekuatan utama untuk membangun set spanning untuk nullspace-nya (yaitu, untuk A x  =  y di atas cincin yang diberikan, membangun basis untuk nullspace dari [  A  |  y  ] dan lihat apakah ada solusi dengan koefisien akhir −1); dan selanjutnya untuk mengurangi konstruksi kekuatan utama nullspaces modulo ke pembuatan nullspaces modulo primes, dan matriks multiplikasi modulo kekuatan utama. Kedua tugas terakhir adalah masalah yang layak untuk comod _k L , asalkan Anda dapat membangun matriks yang terlibat.

Ternyata matriks yang terlibat dalam pengurangan McKenzie dan Cook sendiri dapat dihitung dengan perkalian matriks, dan pembagian (yang terpenting) oleh faktor konstan. Untungnya, untuk kekuatan utama, koefisien matriks yang terlibat dapat dihitung pada pita kerja menggunakan oracle untuk coMod _p L -machines ; dan pembagian dengan konstan dapat dilakukan di NC ¹ , yang lagi layak di comod _p L . Jadi ternyata bahwa seluruh masalah adalah pada akhirnya bisa dilakukan di comod _k L .

Untuk detail selengkapnya, lihat [ arxiv: 1202.3949 ].