Rozważ następujący problem testowania członkostwa w podgrupie abelian .
Wejścia:
Skończona grupa abelowa o dowolnie dużych .
Wytwarzające osadzone podgrupy .
Element .
Wyjście: „tak”, jeżeli i „nie” w innym miejscu.
Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym komputerze? Uważam algorytm efektywny jeśli używa czasu i zasobów pamięci w zwykłym znaczeniu klasycznych maszyn Turinga. Należy zauważyć, że można założyć, dla każdej podgrupy . Rozmiar wejściowy tego problemu wynosi .
Trochę motywacji . Intuicyjnie wygląda na to, że problem można rozwiązać za pomocą algorytmów do rozwiązywania liniowych układów zgodności lub liniowych równań diofantycznych (czytaj poniżej). Wydaje się jednak, że istnieją różne pojęcia wydajności obliczeniowej stosowane w kontekście obliczeń z liczbami całkowitymi, takie jak: silnie versus słabo wielomianowy czas, algebraiczna versus złożoność bitowa. Nie jestem ekspertem od tych definicji i nie mogę znaleźć odniesienia, które jednoznacznie rozstrzygałoby to pytanie.
Aktualizacja: odpowiedź na problem brzmi „tak”.
W późnej odpowiedzi zaproponowałem metodę opartą na normalnych formach Smitha, która jest skuteczna dla każdej grupy o przepisanej formie.
Odpowiedź pokazy blondin, że w szczególności w przypadku, gdy wszystkie są postaci D i = N E i i i N i , e i są liczbami całkowitymi, „małe”, to problem należy do NC 3 ⊂ P . Małe liczby całkowite są wykładniczo małe o wielkości wejściowej: O ( log log | A | ) .
W mojej odpowiedzi użyłem „podgrup ortogonalnych”, aby rozwiązać ten problem, ale uważam, że nie jest to konieczne. Postaram się udzielić bardziej bezpośredniej odpowiedzi w oparciu o metodę, którą czytam w formie formularzy Echelon.
Niektóre możliwe podejścia
Problem jest ściśle związany z rozwiązywaniem liniowego układu zgodności i / lub liniowych równań diofantycznych. Podsumowuję te połączenia w celu uzupełnienia.
Weźmy jako macierz, której kolumny są elementami zestawu generującego { h 1 , … , h n } . Poniższy układ równań
ma rozwiązanie tylko wtedy, gdy .
Jeśli wszystkie czynniki cykliczne mają ten sam wymiar istnieje algorytm oparty na normalnych formach Smitha, który rozwiązuje problem w czasie wielomianowym. W tym przypadku skuteczny algorytm z [1] znajduje normalną postać Smitha : zwraca macierz diagonalną i dwie odwracalne macierze i tak że . Zmniejszyło to problem rozwiązania równoważnego systemu systemowego z przekątnąMożemy skutecznie decydować, czy system ma rozwiązanie wykorzystujące algorytm euklidesowy. A D U V D = U A V D Y = U bD.
Powyższy przykład sugeruje, że problem można skutecznie rozwiązać za pomocą podobnych technik w ogólnym przypadku. Możemy spróbować rozwiązać układ wykonując operacje modułowe lub przekształcając go w większy układ liniowych równań diofantycznych. Niektóre możliwe techniki podejścia do problemu, o których mogę myśleć, to:
- Obliczanie normalnych form według Smitha .
- Obliczanie macierz schodkowa z .
- Całkowita eliminacja Gaussa.
źródło
Odpowiedzi:
Weryfikacja, czy (gdzie są wektorami zgodnie z komentarzami PO) jest równoważne ze sprawdzeniem, czy istnieje rozwiązanie dla tego systemu:b∈⟨h1,…,hn⟩ hi
W twoim przypadku są małymi liczbami (tzn. Ich wartość jest logartihmic w wielkości wejściowej). Niestety nie wydaje się, że możemy założyć, że są małe.e1,…,eN d1,…,dn
Jeśli tak, to możesz znaleźć rozwiązanie dla systemu w z wyniku McKenzie & Cook [1] . Ten artykuł pokazuje, że rozwiązywanie liniowych przystawek modulo liczba całkowita z małymi czynnikami (LCON) jest w . Co więcej, ten problem jest równoważny z problemem członkostwa w grupie permutacji abelowej (AGM). Praca doktorska McKenziego jest w pełni poświęcona tym problemom [1] . Niedawno problemy te zostały rozważone przez Arvind i Vijayaraghavan [3] .NC3 NC3 NC1
[1] Pierre McKenzie i Stephen A. Cook. Równoległa złożoność problemów grup permutacyjnych Abeliana. 1987.
[2] Pierre McKenzie. Równoległe grupy złożoności i permutacji. 1984.
[3] V. Arvind i TC Vijayaraghavan. Klasyfikowanie problemów w liniach zbiegów i grupach permutacji abelowej za pomocą klas zliczania przestrzeni logicznej. 2010 r.
źródło
Po pewnym czasie udało mi się znaleźć być może nieoptymalny, ale prosty algorytm, który dowodzi, że złożoność problemu jest wielomianowa.
Istnieją wydajne algorytmy klasyczne dla problemów (a) i (b) (patrz analiza poniżej). Daje to efektywne członkostwa testu, ponieważ element jest prostopadła do wtedy i tylko wtedy .b H⊥ h∈H
Analiza
Ortogonalna podgrupa jest zdefiniowana poprzez grupę znaków jako: Główne właściwości:H⊥ G
Algorytm dla (a) :
Postępuję zgodnie z algorytmem z [ 1 ] z niewielkimi zmianami. należy do wtedy i tylko wtedy, gdy dla wszystkich , ale liniowo wystarczy pokazać dla każdy generator . Rozszerzanie znaku pod względem wykładniczym (tutaj domyślnie używam cyklicznego rozkładu czynników) warunek ten jest równoważny z Aby rozwiązać te równania, oblicz przy użyciu algorytmu euklidesowego i liczbg H⊥ χg(h)=1 h∈H χb(hi)=1 H
Algorytm dla (b) :
Skoro już wiemy, w jaki sposób obliczyć wytwarzającego-zestaw , to jest łatwe do sprawdzenia, czy dany element należący do . Najpierw oblicz zestaw generatora z . Następnie z definicji należy do wtedy i tylko wtedy, gdy dla wszystkich generatorów . Ponieważ jest ich liczba O (polilog ( )) i można to zrobić skutecznie za pomocą arytmetyki modułowej, jesteśmy gotowi . b H ⟨ g 1 , ... , g y ⟩ H ⊥ b H × B ( g I ) = 1 H ⊥ | G |H⊥ b H ⟨g1,…,gs⟩ H⊥ b H χb(gi)=1 H⊥ |G|
źródło