Czy rozwiązywanie układów równań modulo w dla złożone?

Interesuje mnie złożoność rozwiązywania równań liniowych modulo k , dla dowolnego k (i ze szczególnym zainteresowaniem mocami pierwotnymi), w szczególności:

Problem. Czy dla danego układu równań liniowych w nieznanych modulo istnieją jakieś rozwiązania?n $m$$n$$k$

W streszczeniu swojego artykułu Struktura i znaczenie klas logspace-MOD w klasach Mod _k L , Buntrock, Damm, Hertrampf i Meinel twierdzą, że „ demonstrują swoje znaczenie poprzez udowodnienie, że wszystkie standardowe problemy algebry liniowej nad skończonymi pierścieniami są kompletne dla tych klas$\mathbb Z/k\mathbb Z$ ". Po bliższym przyjrzeniu się historia jest bardziej skomplikowana. Na przykład Buntrock i in. pokaż (na podstawie szkicu próbnego we wcześniejszym i swobodnie dostępnym szkicu znalezionym przez Kaveha, dzięki!), że rozwiązywanie układów równań liniowych należy do klasy komplementarnej coMod _k L , dla kgłówny. Ta klasa nie jest równa Mod _k L dla k kompozytów, ale nieważne, że - martwi mnie fakt, że nie robią oni żadnych uwag na temat tego, czy układy równań liniowych mod k są w ogóle zawarte w coMod _k L dla k kompozytów!

Pytanie: Czy układy równań liniowych modulo k są zawarte w coMod _k L dla wszystkich dodatnich k?

Jeśli potrafisz rozwiązać układy równań modulo o wyższej mocy q liczby pierwszej p , możesz rozwiązać je również modulo p ; więc rozwiązywanie układów równań modulo q jest coMod _p L- twardy . Jeśli mógłbyś wykazać, że ten problem występuje w Mod _q L , skończyłbyś pokazaniem Mod _k L  =  coMod _k L dla wszystkich k . Trudno to udowodnić. Ale czy jest w coMod _k L ?

Jestem szczęśliwy mogąc powiedzieć, że myślę, że możemy odpowiedzieć na to pytanie twierdząco, to znaczy decydując czy liniowy zbieżność jest wykonalne modulo k jest Comod _K L -Complete.

Możemy faktycznie zredukować ten problem do szczególnego przypadku głównych mocy. Można pokazać, że:

Normalna forma. Klasa coMod _k L składa się z języków L w postaci L  =  L _{p 1}  ∩  L _{p 2}  ∩ ... ∩  L _{p r}  , gdzie L _{p j}  ∈  coMod _{p j}  L i gdzie p _j rozciąga się na czynniki pierwsze k .

Według twierdzenia Remaindera każde rozwiązanie układu równań modulo każdej z sił pierwszych dzielące k daje rozwiązanie dla tego samego układu, mod k . Więc jeśli rozwiązywania układów równań liniowych nad jest zawarty w Comod _{p j}  L wynika, że systemy rozwiązywania równań mod k jest zawarty w Comod _k L . p t j$p_{\!j}^{e_j}$$p_{\!j}^{t_j}$

Istnieje standardowy algorytm opisany przez McKenziego i Cooka, służący do zmniejszenia zgodności liniowej modulo siły podstawowej do skonstruowania zestawu rozpinającego dla jego zerowej przestrzeni (mianowicie, dla A x  =  y na danym pierścieniu, zbuduj podstawę dla pustej przestrzeni [  A  |  y  ] i sprawdź, czy istnieją jakieś rozwiązania o końcowym współczynniku -1); a następnie w celu zmniejszenia konstrukcji zerowych mocy modulo liczb pierwszych do konstruowania zerowych przestrzeni modulo liczb pierwszych i mnożenia macierzy modulo liczb pierwszych. Oba te ostatnie zadania są problemami wykonalnymi dla coMod _k L , pod warunkiem, że można zbudować zaangażowane macierze.

Okazuje się, że macierze biorące udział w redukcji McKenziego i Cooka mogą być obliczone przez mnożenie macierzy i (przede wszystkim) dzielenie przez stały współczynnik. Na szczęście dla mocy pierwotnych współczynniki macierzy uczestniczących w obliczeniach można obliczyć na taśmie roboczej za pomocą wyroczni dla maszyn coMod _p L ; i dzielenie przez stałą można przeprowadzić NC ¹ , który znowu jest możliwe w Comod _p L . Tak więc okazuje się, że cały problem jest ostatecznie wykonalne w Comod _k L .

Aby uzyskać szczegółowe informacje, zobacz [ arxiv: 1202.3949 ].