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 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 ". 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 ?
źródło
Odpowiedzi:
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:
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 jpejj ptjj
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 1 , 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 ].
źródło