Złożoność problemu macierzowego

Następujący problem pojawił się ostatnio w moich badaniach. Nie będąc ekspertem od zagadnień algorytmicznych, obszernie poszukiwałem odpowiednich problemów, które można by zmniejszyć. Nie rozumiem, jak działałby 3SAT i chociaż ZOE jest podobny w duchu, redukcja nie jest oczywista. Inną możliwością byłaby egzystencjalna teoria rzeczywistości. To też nie wydaje się pasować, ale mogę się mylić.

Problem: Zarówno $A$ i $B$ są matrykami $n\times n$ nad twoim ulubionym polem. Zakładamy, że dowolny zestaw wskaźników $A$ jest ustawiony na 0. Podobnie, dowolny zestaw wskaźników jest ustawiony na 0. Pytanie: czy możemy wypełnić pozostałe wskaźniki i tak że ? $B$ $A$ $B$ $AB = I_n$

Przykład: , . Niemożliwe. $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$ $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$

Jaka jest złożoność obliczeniowa tego (w )? $n$

Wszelkie wskazówki i pomysły dotyczące tego, gdzie szukać podobnych wyników w literaturze, będą bardzo mile widziane.

EDYCJA (całkowicie zapomniałem o tym poście): W najnowszej pracy, która jest dostępna na arXiv (jeśli ktoś jest zainteresowany przedrukiem, daj mi znać) pokazaliśmy, że problem jest NP trudny w stosunku do dowolnego skończonego pola.

cc.complexity-theory

— MB
źródło

Pod warunkiem, że pole podstawowe jest wystarczająco duże, problem ze sprawdzeniem, czy można zrobić

odwracalnym

zmniejsza się do (uzupełnienia) testu tożsamości wielomianowej. Zauważ tylko, że wyznacznik

jest wielomianem w wartościach brakujących wpisów. AB $AB$

AB $AB$

— Andrew Morgan,

Również przypadek, w którym ograniczamy wpisy

do zera jeden, a charakterystyka pola jest większa niż

, redukuje się do dwustronnego idealnego dopasowania. Można sobie wyobrazić, zbierając dla każdego indeksu

inny wskaźnik

tak, że można ustawić

, a pozostałe wpisy zero. (Umieszczenie większej liczby wartości niż to może tylko zaszkodzić.) Następnie warunek

można wyrazić jako wykres dwudzielny ze wskaźnikami

ZA $A$

b $B$

n $n$

ja $i$

kja $k_i$

ZAja , kja= Bkja, ja= 1 $A_{i,k_i} = B_{k_i,i} = 1$

AB=In $AB = I_n$

i $i$ Po lewej wyborów

po prawej stronie, a krawędziami

par, dla których możemy ustawić

. ki $k_i$

(i,ki) $(i,k_i)$

Ai,ki $A_{i,k_i}$

Bki,i $B_{k_i,i}$

— Andrew Morgan,

@MB: Należy również pamiętać, że podczas sprawdzania czy

może być wykonane odwracalna jest taka sama, jak sprawdzenie, czy oba i

może oddzielnie być odwracalna, sprawdzając czy

może być wykonane odwracalna nie jest taka sama, jak sprawdzenie, czy

może być wykonane tożsamość

AB $AB$

A $A$

B $B$

AB $AB$

AB $AB$ . Aby sprawdzić, czy

(względnie

) można przekształcić w odwracalne, powiesz „że można to zrobić skutecznie”, ale w twoim otoczeniu jest to równoważne ze sprawdzeniem, czy istnieje idealne dopasowanie pomiędzy wsparciem

(odpowiednio

A $A$

B $B$

A $A$

B $B$ ) (ten sam problem, ale nieco inne ustawienie od drugiego komentarza Andrew Morgana).

— Joshua Grochow

Wydaje się, że jakiś szczególny przypadek tego problemu występuje w PPAD, np. Problem liniowej komplementarności: kintali.wordpress.com/2009/08/04/linear-complementarity-prob‌ lem To pokazałoby, że znalezienie rozwiązania jest trudne.

— domotorp

W przypadku, gdy inni jeszcze tego nie zrozumieli, istnieje wybór

(ponad dowolną dziedziną), dla których

, ale dla których test doskonałego dopasowania kończy się niepowodzeniem. to znaczy nie ma matrycę permutacji

tak, że

jest podtrzymywany na poparcie

jest osadzony na poparcie

. Wyboru podaje

iA,B $A,B$

AB=I $AB = I$

P $P$

A $A$

P−1=P⊺ $P^{-1}=P^{\intercal}$

B $B$

A=⎡⎣⎢111−10−1011⎤⎦⎥ $A=\begin{bmatrix}1&-1&0\\1&0&1\\1&-1&1\end{bmatrix}$

. B=⎡⎣⎢10−1110−1−11⎤⎦⎥ $B=\begin{bmatrix}1&1&-1\\0&1&-1\\-1&0&1\end{bmatrix}$

— Andrew Morgan

Również tu jest nie-straszne górnej związaniu : lub przyjmując hipotezę Riemanna . Wynika to z tego, że dla dowolnych podanych wzorów zer dla sprawdzenie, czy można zrobić sprawdza, czy pewien układ równań wielomianowych ma rozwiązanie w , i można to zrobić w tych górnych granice autorstwa Koirana. $\mathbb{C}$ $\mathsf{PSPACE}$ $\mathsf{AM}$ $A,B$ $AB=I_n$ $n^2$ $\mathbb{C}$

Innym podejściem jest próba wykorzystania faktu, że jest to w rzeczywistości układ równań dwuliniowych . Rozwiązywanie równań dwuliniowych jest równoznaczne ze znalezieniem rozwiązań „rangi 1” równań liniowych. Próbowałem ustalić, czy istnieją lepsze górne granice dla rozwiązywania układów dwuliniowych w ogóle, ale jak dotąd bez powodzenia. Możliwe jest również, że można wykorzystać konkretną strukturę tych równań dwuliniowych, aby uzyskać coś lepszego niż to, co ogólnie wiadomo ...

— Joshua Grochow
źródło

Czy PSPACE nie wynika z problemu związanego z NP?

— MB

@ MB: W przypadku pól skończonych problem jest oczywiście w NP (wystarczy pokazać ustawienie zmiennych), co stanowi lepszą górną granicę niż AM. Kiedy dane wejściowe są liczbami całkowitymi, ale prosisz o rozwiązanie w liczbach zespolonych, kiedy istnieje rozwiązanie, nie jest nawet oczywiste, że możesz zapisać je w dowolnej skończonej ilości pamięci, nie mówiąc już o wielomianach.

— Joshua Grochow