Złożoność problemu macierzowego

21

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, jakA i BB są matrykami n × nn×n nad twoim ulubionym polem. Zakładamy, że dowolny zestaw wskaźników AA 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 ?bBA AB BA B = I nAB=In

Przykład: , . Niemożliwe.A = [ 0 a 1 a 2 0 ]A=[0a2a10] B = [ b 1 0 0 b 2 ]B=[b100b2]

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

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
4
Pod warunkiem, że pole podstawowe jest wystarczająco duże, problem ze sprawdzeniem, czy można zrobić Aodwracalnym B, zmniejsza się do (uzupełnienia) testu tożsamości wielomianowej. Zauważ tylko, że wyznacznik A B jest wielomianem w wartościach brakujących wpisów. ABAB
Andrew Morgan,
3
Również przypadek, w którym ograniczamy wpisy A i B do zera jeden, a charakterystyka pola jest większa niż n , redukuje się do dwustronnego idealnego dopasowania. Można sobie wyobrazić, zbierając dla każdego indeksu i inny wskaźnik k I tak, że można ustawić A ja , k i = B k I , i = 1 , a pozostałe wpisy zero. (Umieszczenie większej liczby wartości niż to może tylko zaszkodzić.) Następnie warunek A B = I n można wyrazić jako wykres dwudzielny ze wskaźnikami iZAbnjakjaZAja , kja= Bkja, ja= 1AB=IniPo lewej wyborów k i po prawej stronie, a krawędziami ( i , k I ) par, dla których możemy ustawić ja , k I i B k ja , ja . ki(i,ki)Ai,kiBki,i
Andrew Morgan,
2
@MB: Należy również pamiętać, że podczas sprawdzania czy B może być wykonane odwracalna jest taka sama, jak sprawdzenie, czy oba i B może oddzielnie być odwracalna, sprawdzając czy B może być wykonane odwracalna nie jest taka sama, jak sprawdzenie, czy B może być wykonane tożsamośćABABABAB . Aby sprawdzić, czy A (względnie B ) 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 A (odpowiednio BABAB) (ten sam problem, ale nieco inne ustawienie od drugiego komentarza Andrew Morgana).
Joshua Grochow
2
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
2
W przypadku, gdy inni jeszcze tego nie zrozumieli, istnieje wybór A , B (ponad dowolną dziedziną), dla których A B = I , ale dla których test doskonałego dopasowania kończy się niepowodzeniem. to znaczy nie ma matrycę permutacji P tak, że P jest podtrzymywany na poparcie A i P - 1 = P ⊺ jest osadzony na poparcie B . Wyboru podaje A = [ 1 - 1 0 1 0 1 1 - 1 1 ] iA,BAB=IPPAP−1=P⊺BA=⎡⎣⎢111−10−1011⎤⎦⎥ B = [ 1 1 - 1 0 1 - 1 - 1 0 1 ]. B=⎡⎣⎢10−1110−1−11⎤⎦⎥
Andrew Morgan

Odpowiedzi:

8

Również tu jest nie-straszne górnej związaniu C : P S P A C E lub przyjmując hipotezę Riemanna A M . Wynika to z tego, że dla dowolnych podanych wzorów zer dla A , B sprawdzenie, czy można zrobić A B = I n, sprawdza, czy pewien układ n 2 równań wielomianowych ma rozwiązanie w C , i można to zrobić w tych górnych granice autorstwa Koirana.CPSPACEAMA,BAB=Inn2C

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
2
@ 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