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

19

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 kmnk

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 klasZ/kZ ". 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 ?

Niel de Beaudrap
źródło
link citeseerx do szkicu artykułu . ps: bardziej solidnym sposobem radzenia sobie z modk jest użycie modkA gdzie A[k1] to zestaw zaakceptowanych przypomnień modk . Istnieje również powiązane pytanie dotyczące złożoności dowodu, por. „ Dowód złożoności algebry liniowej ” autorstwa Soltysa i Cooka, APAL 2004.
Kaveh
2
co z samym k = 4 i parzystością-L?
domotorp

Odpowiedzi:

9

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 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 L wynika, że systemy rozwiązywania równań mod k jest zawarty w Comod k L . p t jpjejpjtj

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 ].

Niel de Beaudrap
źródło
Chciałbym wiedzieć, czy to stała w swojej zapytania / odpowiedzi? Interesuje mnie przypadek, w którym rozmiar nie jest nieograniczony. kkk
Juan Bermejo Vega
1
@Juan: Tak, jest stałą, choć dowolną stałą. k
Niel de Beaudrap