Złożoność osiągalności w liniowych układach dynamicznych nad polami skończonymi

Niech $A$ będzie macierzą nad polem skończonym $\mathbb{F}_2 = \{0,1\}$ a $x$ , $y$ będą wektorami przestrzeni $\mathbb{F}_2^n$ . Interesuje mnie złożoność obliczeniowa przy podejmowaniu decyzji, czy istnieje $t \in \mathbb{N}$ takie, że $A^t x = y$ , tj. Problem osiągalności liniowych układów dynamicznych nad polami skończonymi.

Problem ten jest wyraźnie $\mathbf{NP}$ (przypuszczenie $0 \le t < 2^n$ i obliczyć T w czasie wielomianowym przez wielokrotne kwadratury). Ja i moi współpracownicy byli w stanie wykazać N P -completeness związanego z tym problemu ustalenia, czy istnieje t ∈ N , tak że t x ≥ Y , gdzie ≥ jest componentwise nierówności.$A^t$$\mathbf{NP}$$t \in \mathbb{N}$$A^t x \ge y$$\ge$

Problem ten wydaje się dość naturalny, ale nie udało mi się znaleźć w literaturze odniesień do jego złożoności obliczeniowej, prawdopodobnie dlatego, że nie znam dokładnej terminologii. Czy wiesz, czy problem z równości jest $\mathbf{NP}$ -Complete lub jeśli to jest rzeczywiście w $\mathbf{P}$ ?

Dla jasności uogólnię twoje pytanie, aby przekroczyło charakterystykę (z polem bazowym F q ) zamiast konkretnego przypadku p = q = 2 . Przyjmę p i q jako stałe; Zostawię czytelnikowi, aby dowiedzieć się, jaka jest dokładna zależność od tych parametrów, ponieważ istnieje kilka kompromisów, które można wprowadzić. Rezultat końcowy jest taki, że twój problem jest w przybliżeniu równoważny dyskretnemu problemowi z logami dla skończonych pól charakterystyki p .$p > 0$$\mathbb{F}_q$$p=q=2$$p$$q$$p$

Aby być bardziej konkretny, niech zwykły dyskretnego problemu dziennika nad rozszerzeniami być, biorąc pod uwagę pole rozszerzenie F z F q , a , b ∈ F , odnaleźć dowolny całkowitą t tak, że = b T lub raport, że żaden istnieje . Niech silne dyskretne problemem log na przedłużenie F q być, zważywszy, F , a , b, tak jak poprzednio, znaleźć liczby całkowite Z , m , tak aby $\mathbb{F}_q$$\mathbb{F}$$\mathbb{F}_q$$a,b \in \mathbb{F}$$t$$a = b^t$$\mathbb{F}_q$$\mathbb{F},a,b$$z,m$ dla liczby całkowitej t ifflub zgłoś, że nieistnieje. Następnie istnieją następujące redukcje:$a = b^t$$t$$t = z \pmod{m}$$t$

• Istnieje deterministyczne ograniczenie mapowania z dyskretnego dziennika nad rozszerzeniami do twojego problemu.$\mathbb{F}_q$

• Istnieje skuteczny, deterministyczny algorytm, który rozwiązuje twój problem, gdy masz dostęp do wyroczni obliczającej silny dyskretny problem dziennika nad rozszerzeniami .$\mathbb{F}_q$

W związku z tym uważam, że jest mało prawdopodobne, aby ktoś opublikował dowód twardość lub dowód, że twój problem jest w w najbliższej przyszłości.$\mathsf{NP}$$\mathsf{P}$

Uwaga: Silny problem z logami dyskretnymi dotyczącymi rozszerzeń można zredukować do Turinga do pozornie słabszej postaci (choć nadal wydaje się silniejszy niż zwykły problem z logami dyskretnymi): Biorąc pod uwagę pole rozszerzenia z oraz , znajdź najmniejszą, nieujemną liczbę całkowitą , aby . Wynika to z faktu, że rząd wynosi jeden plus najmniejszy nieujemny tak że .F F q a,b∈ F ta= b t bt b - 1 = b $\mathbb{F}_q$$\mathbb{F}$$\mathbb{F}_q$$a,b \in \mathbb{F}$$t$$a = b^t$$b$$t$$b^{-1} = b^t$

---

Pierwsza redukcja: Twierdzenie jest takie, że zwykły dyskretny problem dziennika dotyczący rozszerzeń mapowania redukuje do tego problemu. Wynika to z faktu, że mnożenie w jest transformacją liniową, gdy widzimy jako wymiarową przestrzeń wektorową nad . Stąd pytanie o postać nad staje się nad , gdzie są wymiarowymi wektorami, a jestF q n F q n n F q a= b t F q n → a = B t → e F q → a , → e nBn×n F q → a aBb → e 1∈ F q n p=q=2$\mathbb{F}_{q}$$\mathbb{F}_{q^n}$$\mathbb{F}_{q^n}$$n$$\mathbb{F}_q$$a = b^t$$\mathbb{F}_{q^n}$$\vec{a} = B^t\vec{e}$$\mathbb{F}_q$$\vec{a},\vec{e}$$n$$B$$n\times n$macierz, cała . Wektor może być łatwo obliczony z , od , a tylko przedstawienie , która może być zapisana skutecznie . Wydaje się, że nadal jest to trudny przypadek ogólnego problemu z logami dyskretnymi, nawet przy (ale oczywiście rośnie ). W szczególności ludzie nadal konkurują ze sobą, aby zobaczyć, jak daleko mogą to obliczyć.$\mathbb{F}_q$$\vec{a}$$a$$B$$b$$\vec{e}$$1 \in \mathbb{F}_{q^n}$$p=q=2$$n$

---

Druga redukcja: twierdzenie jest takie, że twój problem sprowadza się do silnego problemu z logiem dyskretnym dotyczącym rozszerzeń . Ta redukcja ma kilka elementów, więc wybacz długość. Niech dane wejściowe będą wymiarowymi wektorami i macierzy , w całym ; celem jest znalezienie , aby . nx,yn×nA F q ty= A t$\mathbb{F}_q$$n$$x,y$$n\times n$$A$$\mathbb{F}_q$$t$$y = A^tx$

Podstawową ideą jest napisanie w postaci kanonicznej Jordana (JCF), z której możemy zredukować testowanie do silnego problemu z logami dyskretnymi za pomocą prostej algebry.y = A t$A$$y = A^tx$

Jednym z powodów użycia formy kanonicznej podobieństwa macierzy jest to, że jeśli , to . W związku z tym można przekształcić do , w którym teraz jest w postaci znacznie przyjemniejsze niż arbitralne . JCF jest szczególnie prostą formą, która umożliwia resztę algorytmu. Odtąd załóżmy, że jest już w JCF, ale pozwól również, aby i mogły mieć wpisy w polu rozszerzenia .A t = P - 1 J t P y = A t x ( P y ) = J t ( P x ) J A A x , y , A F$A = P^{-1}JP$$A^t = P^{-1}J^tP$$y = A^tx$$(Py) = J^t(Px)$$J$$A$$A$$x,y,$$A$$\mathbb{F}_q$

Uwaga: Istnieją pewne subtelności wynikające z pracy z JCF. W szczególności że możemy wykonywać operacje terenowe w dowolnym rozszerzeniu (bez względu na to, jak duże) w jednym kroku czasowym i że możemy efektywnie obliczyć JCF. a priori jest to nierealne, ponieważ praca z JCF może wymagać pracy w polu rozszerzającym (polu podziału charakterystycznego wielomianu) o stopniu wykładniczym. Jednak z pewną ostrożnością i korzystając z faktu, że pracujemy nad skończonym polem, możemy obejść te problemy. W szczególności skojarzymy z każdym blokiem Jordana pole stopnia co najwyżej ponadF ′ n F q xy F ′ F ′ F$\mathbb{F}_q$$\mathbb{F}'$$n$$\mathbb{F}_q$ tak aby wszystkie wpisy w bloku Jordana i odpowiadające im elementy , znajdowały się w . Pole może różnić się w zależności od bloku, ale użycie tej `` mieszanej reprezentacji' 'pozwala na skuteczny opis JCF, który ponadto można skutecznie znaleźć. Algorytm opisany w pozostałej części tej sekcji musi działać tylko z jednym blokiem na raz, tak długo, jak wykonuje swoje operacje w polu w powiązanym polu , algorytm będzie wydajny. [uwaga końcowa]$x$$y$$\mathbb{F}'$$\mathbb{F}'$$\mathbb{F}'$

Zastosowanie JCF daje nam równania o następującej formie, przy czym każde równanie odpowiada blokowi Jordana:

$$\begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{k-1} \\ y_{k} \\ \end{bmatrix} = \begin{bmatrix} \lambda & 1 & & & & \\ & \lambda & 1 & & & \\ & & \lambda & 1 & & \\ & & & \ddots & & \\ & & & & \lambda & 1 \\ & & & & & \lambda \\ \end{bmatrix}^t \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{k-1} \\ x_{k} \\ \end{bmatrix}$$

Algorytm będzie obsługiwał każdy blok osobno. W ogólnym przypadku dla każdego bloku będziemy mieli zapytanie o naszą silną dyskretną wyrocznię z dziennika, z której wyrocznia poinformuje nas o warunku modułowości, . . Otrzymamy również zestaw , aby musiał trzymać . Po przetworzeniu wszystkich bloków musimy sprawdzić, czy istnieje wybór który spełnia kombinacje wszystkich tych warunków. Można to zrobić poprzez zapewnienie jest wspólnym elementem wszystkich zestawów tak, że równania iS ⊆ { 0 , 1 , ⋯ , p - 1 } ⋁ s ∈ S [ t = $t = z \pmod{m}$$S \subseteq \{0,1,\cdots,p-1\}$ t s S t = $\bigvee_{s\in S}\left[ t = s \pmod{p} \right]$$t$$s$$S$t = z $t = s \pmod p$$t = z_j \pmod{m_j}$są jednocześnie spełnione, gdzie rozciąga się na bloki.$j$

Istnieją również specjalne przypadki, które pojawiają się podczas całej procedury. W takich przypadkach dostaniemy warunków formie jakiegoś wartości lub formularza dla niektórych specyficznych liczba całkowita , z niektórych blokach, albo może nawet okazać, że nie może istnieć . Można je bez problemu włączyć do logiki ogólnego przypadku.ℓ t = s s $t > \ell$$\ell$$t = s$$s$$t$

Teraz opisujemy podprocedurę do obsługi każdego bloku Jordana. Napraw taki blok.

Zacznij od skupienia się na ostatniej współrzędnej w bloku. Warunek wymaga, aby . Innymi słowy, jest to instancja problemu dziennika dyskretnego w pewnym rozszerzeniu pola . Następnie używamy wyroczni, aby go rozwiązać, co albo nie daje żadnego rozwiązania, albo daje warunek modułowości dla . Jeśli nie zostanie zwrócone „brak rozwiązania”, zwracamy informację o tym. W przeciwnym razie otrzymamy warunek , który jest równoważny .y k = λ t x k F q t t = $y = A^tx$$y_k = \lambda^t x_k$$\mathbb{F}_q$$t$y k = λ t x $t = z \pmod{m}$$y_k = \lambda^t x_k$

Aby obsłużyć inne współrzędne, zaczynamy od następującej formuły (patrz np. Tutaj ): xk=0yk=λtxkyk=0k-1xy(k-1)×(k-1)xk≠

$$\begin{bmatrix} \lambda & 1 & & & & \\ & \lambda & 1 & & & \\ & & \lambda & 1 & & \\ & & & \ddots & & \\ & & & & \lambda & 1 \\ & & & & & \lambda \\ \end{bmatrix}^t = \begin{bmatrix} \lambda^t & \binom{t}{1}\lambda^{t-1} & \binom{t}{2}\lambda^{t-2} & \cdots & \cdots & \binom{t}{k-1}\lambda^{t-k+1} \\ & \lambda^t & \binom{t}{1}\lambda^{t-1} & \cdots & \cdots & \binom{t}{k-2}\lambda^{t-k+2} \\ & & \ddots & \ddots & \vdots & \vdots\\ & & & \ddots & \ddots & \vdots\\ & & & & \lambda^t & \binom{t}{1}\lambda^{t-1}\\ & & & & & \lambda^t \end{bmatrix}$$ \ ddots & \ ddots & \ vdots \\ & & & & & lambda ^ t & \ binom {t} {1} \ lambda ^ {t-1} \\ & & & & & lambda ^ t \ end {bmatrix } Najpierw zajmijmy się przypadkiem, w którym$x_k = 0$ . Ponieważ mamy już warunek modułowości, który implikuje , możemy założyć, że również. Ale potem możemy po prostu zredukować się do skupiania się na pierwszych wpisach i oraz na górnej lewej submatrix bloku Jordana. Więc od teraz załóżmy, że .$y_k = \lambda^t x_k$$y_k = 0$$k-1$$x$$y$$(k-1)\times (k-1)$$x_k \ne 0$

Po drugie, zajmiemy się przypadkiem, w którym . W tym przypadku potęgi bloku Jordana mają specjalną postać i wymuszają albo dla niektórych , albo , bez żadnych innych warunków. Nie będę omawiać tych spraw, ale wystarczy powiedzieć, że każdy z nich można skutecznie sprawdzić. (Alternatywnie możemy ograniczyć się do przypadku, w którym jest odwracalny; patrz mój komentarz do pytania.)t = z z ≤ k t > k $\lambda = 0$$t = z$$z \le k$$t > k$$A$

Wreszcie dochodzimy do ogólnej sprawy. Ponieważ mamy już warunek modułowości, który implikuje, że , możemy założyć, że warunek się utrzymuje i użyć jako stand-in dla . Mówiąc bardziej ogólnie, możemy użyć do reprezentowania . Dlatego musimy sprawdzić, czy następujący system ma pewien wybór : $y_k = \lambda^t x_k$$y_k x_k^{-1}$$\lambda^t$$y_kx_k^{-1}\lambda^{-z}$$\lambda^{t-z}$$t$

$$\begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{k-1} \\ y_{k} \\ \end{bmatrix} = \begin{bmatrix} y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \binom{t}{2}y_kx_k^{-1}\lambda^{-2} & \cdots & \cdots & \binom{t}{k-1}y_kx_k^{-1}\lambda^{-(k-1)} \\ & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \cdots & \cdots & \binom{t}{k-2}y_kx_k^{-1}\lambda^{-(k-2)} \\ & & \ddots & \ddots & \vdots & \vdots\\ & & & \ddots & \ddots & \vdots\\ & & & & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1}\\ & & & & & y_kx_k^{-1} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{k-1} \\ x_{k} \\ \end{bmatrix}$$ y_kx_k ^ {- 1} \ koniec {bmatrix} \ {zaczynać bmatrix} X_1 \\ x_2 \\ x_3 \\ \ vdots \\ x_ {K-1} \\ x_ {k} \\ \ koniec {bmatrix} Zauważmy, że to, czy równanie się zachowuje, zależy tylko od ; dzieje się tak, ponieważ zależność od jest tylko wielomianowa, $t \pmod{p}$$t$$t$ musi być liczbą całkowitą, a powyższe równania dotyczą pola charakterystyki . Dlatego możemy po prostu wypróbować każdą wartość osobno. Zestaw , który powrócimy, to tylko wybory dla których system jest spełniony.$p$$t \in \{0,1,\ldots,p-1\}$$S$$t$

Tak więc teraz, z wyjątkiem niektórych szczególnych przypadków, podprocedura dla bloku znalazła warunek modułowości i zestaw tak że jeden z musi zostać zachowany dla niektórych . Warunki te są równoważne w tym konkretnym bloku Jordana. Zwracamy je więc z podprocedury. W szczególnych przypadkach albo dochodzi do wniosku, że nie może istnieć (w którym to przypadku podprocedura natychmiast zwraca informację o tym), albo mamy warunek modułowości i pewne warunki specjalne, takie jak dla liczby całkowitej lub dla jakiejś liczby całkowitej$t = a \pmod{m}$$S$$t = s \pmod{p}$$s \in S$$y = A^tx$$t$$t = a \pmod{m}$$t = s$$s$$t > \ell$$\ell$ . W każdym razie wszystkie warunki są równoważne w tym bloku Jordana. Tak więc, jak wspomniano powyżej, podprocedura po prostu zwraca te warunki.$y = A^tx$

Na tym kończy się specyfikacja podprocedury na blok oraz całego algorytmu. Jego poprawność i skuteczność wynikają z poprzedniej dyskusji.

---

Subtelności z wykorzystaniem JCF w drugiej redukcji: Jak wspomniano w drugiej redukcji, istnieją pewne subtelności, które wynikają z pracy z JCF. Istnieje kilka uwag na temat łagodzenia tych problemów:

• Rozszerzenia pól skończonych są normalne . Oznacza to, że jest nieredukowalną wielomian przez , a każde przedłużenie zawierający pierwiastek zawiera wszystkie korzenie . Innymi słowy, pole rozszczepienie nieredukowalnego wielomianu stopnia ma tytuł tylko nad .$P$$\mathbb{F}_q$$\mathbb{F}_q$$P$$P$$P$$d$$d$$\mathbb{F}_q$

• Istnieje uogólnienie jordańskiej formy kanonicznej, zwanej pierwotną racjonalną formą kanoniczną (PRCF), która nie wymaga spisywania rozszerzeń pól. W szczególności, jeśli jest macierzą z wpisami w , to możemy napisać dla niektórych macierzy z wpisami w , gdzie ponadto jest w PRCF. Dodatkowo, jeśli udajemy, że wpisy żyją w polu rozszerzającym który zawiera wszystkie wartości własne , to$A$$\mathbb{F}_q$$A = P^{-1}QP$$P,Q$$\mathbb{F}_q$$Q$$A$$\mathbb{F}'$$\mathbb{F}_q$$A$$Q$będzie w rzeczywistości w JCF. Zatem możemy postrzegać obliczanie JCF jako szczególny przypadek obliczania PRCF.$A$

• Korzystając z formularza PRCF, możemy uwzględnić obliczanie JCF dla jako$A$

  1. obliczanie PRCF przez$A$$\mathbb{F}_q$

  2. obliczanie PRCF każdego bloku (zapożyczenie zapisu z artykułu z Wikipedii) w PRCF , nad polem rozszerzenia , gdzie jest wybrany tak, aby zawierał wszystkie wartości własne$C$$A$$\mathbb{F}'$$\mathbb{F}'$$C$

  Kluczową zaletą tej faktoryzacji jest to, że charakterystyczne wielomianów bloków wszystkie będą nieredukowalne , a zatem dzięki naszej pierwszej obserwacji możemy wybrać aby uzyskać stopień wielkości (co najwyżej ) ponad . Minusem jest to, że teraz musimy używać różnych pól rozszerzeń do reprezentowania każdego bloku JCF, więc reprezentacja jest nietypowa i skomplikowana.$C$$\mathbb{F}'$$C$$n$$\mathbb{F}_q$

Zatem, biorąc pod uwagę możliwość wydajnego obliczenia PRCF, możemy efektywnie obliczyć odpowiednie kodowanie JCF, a kodowanie to jest takie, że praca z dowolnym konkretnym blokiem JCF może być wykonana w polu rozszerzenia co najwyżej ponad .$n$$\mathbb{F}_n$

Ponieważ do obliczenia PRCF efektywnie papier „ Rational postaci kanonicznej algorytm ” (KR Matthews Math. Bohemica 117 (1992), 315-324) umożliwia skuteczną algorytm obliczyć PRCF gdy faktoryzacji charakterystycznej wielomianu jest znany . Aby ustalić stałą charakterystykę (taką jak my), faktoring wielomianów wielowymiarowych nad polami skończonymi można wykonać w deterministycznym czasie wielomianowym (patrz np. „ O nowym algorytmie faktoryzacji dla wielomianów nad polami skończonymi ” (H. Niederreitter i R. Gottfert, Math. Z Computation 64 (1995) 347-353).), Dzięki czemu PRCF można obliczyć wydajnie.$A$