Czy problem z wypełnieniem do połowy magicznego kwadratu NP-jest kompletny?

Oto problem:

W niektórych komórkach mamy kwadrat z niektórymi liczbami od 1..N. Trzeba ustalić, czy można go ukończyć na magiczny kwadrat.

Przykłady:

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _ 
9 _ _  >>>  NO SOLUTION 
8 _ _

Czy ten problem NP-jest kompletny? Jeśli tak, jak mogę to udowodnić?

Crosspost w stwardnieniu rozsianym

cc.complexity-theory np-hardness np puzzles

— levanovd
źródło

Nie, proszenie o pomoc nie jest niczym złym. Ale twoje pytanie musi należeć do zakresu witryny, o którą pytałeś. Myślę, że Math SE jest odpowiedni do tego pytania, a TCS SE nie.

— Hsien-Chih Chang 之之

Przyjmujemy pytania dotyczące udowodnienia twardości NP, szczególnie gdy problem jest trudny. Weźmy na przykład trzy przykłady wymienione tutaj jako odpowiedzi: meta.cstheory.stackexchange.com/questions/784/…

— Suresh Venkat

Jeśli to zadanie domowe, nie pozwalamy na to, bez względu na to, czy jest to nieetyczne.

— Peter Shor,

@levanovd: To nie jest stackoverflow. Ta społeczność ma wyraźne zasady zabraniające zadawania zadań domowych. Nie ma tutaj znaczenia fakt, że w przepełnieniu stosu obowiązują inne zasady.

— Jeffε

Nie znam rozwiązania i nie sądzę, że jest to zadanie domowe. Jednak może mi brakować czegoś prostego. Dlatego jeśli ktoś zna kompletne rozwiązanie i uważa, że to pytanie dotyczy zadań domowych, proszę to powiedzieć. Tymczasem założę, że to pytanie nie jest pracą domową, a znacznik [praca domowa] zastosowany w Math SE i wcześniejszy komentarz levanovda były po prostu błędami.

— Tsuyoshi Ito,

Wypełnianie częściowo wypełnionego łacińskiego kwadratu jest NP-Complete. „Złożoność wykonywania częściowych kwadratów łacińskich” Charles J. Colbourn. Discrete Applied Mathematics, tom 8, wydanie 1, kwiecień 1984, strony 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Czy problem kwadratu łacińskiego można przekształcić w zagadnienie magicznego kwadratu za pomocą arytmetyki modułowej? Moja intuicja mówi „tak”, ale reszta mojego mózgu mówi „Wróć do oceniania!”

— Peter Boothe
źródło

Byłoby miło przekształcić to w rygorystyczny argument. Nie jest dla mnie wcale jasne, w jaki sposób arytmetyka modularna naprawdę pomogłaby w zmniejszeniu ZAKOŃCZENIA KWADRATU ŁACIŃSKIEGO do ZAKOŃCZENIA KWADRATU MAGICZNEGO lub odwrotnie. Byłoby raczej ładnie, gdyby można go było uruchomić.

— András Salamon,

To pytanie składa się z dwóch części: po pierwsze, czy problem dotyczy NP, a po drugie, czy NP jest trudny?

W pierwszej części mam pozytywną odpowiedź z nieoczywistym dowodem. (Podziękowania dla Suresha za wskazanie wcześniejszego błędu.)

Rozważ następujący sposób sformalizowania pytania jako problemu decyzyjnego:

NIEOGRANICZONE ZAKOŃCZENIE KWADRATU MAGICZNEGO Dane
wejściowe: liczba całkowita dodatnia podana unarnie, lista liczb całkowitych z ich pozycjami na siatce przez Pytanie: czy istnieją liczby całkowite dla pozostałych pozycji w siatce, aby układ tworzył magiczny kwadrat ? $n$ $n$ $n$

Jeśli dodamy ograniczenie, że każda z liczb całkowitych musi wystąpić dokładnie raz na magicznym kwadracie, wówczas wynikający z tego problem decyzyjny ZAKOŃCZENIE KWADRATU MAGICZNEGO jest oczywiście w NP. Definicja magicznym placu w 1911 roku Encyclopaedia Britannica , po Euler ma tego ograniczenia; w przeciwieństwie do tego, artykuł z Wikipedii używa obecnie terminologii „normalny magiczny kwadrat” i rezerwuje „magiczny kwadrat” dla nieograniczonej wersji. $1,2,\dots,n^2$

Z przez siatki, przynajmniej numery muszą być podane, w przeciwnym razie odpowiedź brzmi trywialnie „TAK” dla nieograniczonego wersji. Można zatem założyć, że rozmiar danych wejściowych wymaga w tym przypadku więcej niż bitów. W normalnej wersji możliwe jest, że istnieją dane wejściowe, które wymagają kilku bitów, ale nie mają rozwiązania; aby uniknąć takich komplikacji, określiłem, że jest podany unarnie. $n$ $n$ $n$ $n$ $n$

Argument wykorzystuje ograniczenie możliwego rozmiaru liczb całkowitych pojawiających się w rozwiązaniach. W normalnym przypadku granica ta jest oczywiście , ale w ogólnym przypadku nie jest z góry oczywiste, że taka granica istnieje. Okazuje się, że istnieje wykładnicza granica. $n^2$

Twierdzenie ( Tyszka, Twierdzenie 12 ): Dowolny układ równań diofantycznych obejmujący równania w postaci i , dla , albo nie ma rozwiązania liczb całkowitych lub ma rozwiązanie, w którym każdy jest liczbą całkowitą i co najwyżej w wartości bezwzględnej. $x_i = 1$ $x_i = x_j + x_k$ $i,j,k \in \{1,2,\dots,n\}$ $x_i$ $\sqrt{5}^{n-1}$

Pojawiło się to również jako Twierdzenie 4.7 w:

Apoloniusz Tyszka, Dwie przypuszczenia dotyczące arytmetyki w R i C , Matematyka. Log. Kwarta. 56 175–184, 2010.

Cipu ogłosił niedawno asymptotycznie lepszą granicę . (Zauważ, że najmniejsze możliwe ograniczenie to ). Argument opiera się na ograniczeniu na wyznaczniku macierzy, ze względu na Waldiego. $2^n$ $2^{n-1}$

Twierdzenie (CIPU 2011) Każdy układ równań diofantycznych udziałem równania postaci i dla , albo ma brak rozwiązania liczb całkowitych lub rozwiązanie, w którym każdy jest liczbą całkowitą i co najwyżej w wartości bezwzględnej. $x_i = 1$ $x_i = x_j + x_k$ $i,j,k \in \{1,2,\dots,n\}$ $x_i$ $2^n$

Jeszcze niedawno Freitas, Friedland i Porta wykazali, że granica , jako następstwo ich bardziej ogólnego Twierdzenia 1.1. $2^{n-1}$

Daje to:

Następstwo: jeśli wystąpienie NIEOGRANICZONEGO ZAKOŃCZENIA KWADRATU MAGICZNEGO o rozmiarze ma rozwiązanie, to ma rozwiązanie wykorzystujące tylko liczby do . $N$ $2^{O(N^2)}$

Oznacza to, że można użyć spacji aby odgadnąć rozwiązanie do granicy, a następnie sprawdzić w czasie czy jest to rozwiązanie. Dokładny wielomian zależy od tego, czy do wyznaczenia używa się wyniku Tyszki, czy Cipu, oraz od tego, jak wyraża się układ diofantyczny równań reprezentujących magiczny kwadrat. W obu przypadkach liczba zmiennych wymaganych w układzie diofantynowym w postaci przedstawionej przez Tyszkę wynosi nie więcej niż . Osiąga się to za pomocą zmiennych dla sum częściowych dla każdego rzędu, kolumny i przekątnej oraz dużej zmiennej łącznej łączącej je razem. Poza samym kwadratem magicznym wymagana jest kolejna wielomianowa liczba zmiennych dla liczb w kwadracie: liczba wymagająca $O(N^4)$ $O(N^8)$ $n^2 + 2(n+1)(n-2)+1 = 3n^2-2n-3$ $n-2$ $m$ bitów można przedstawić za pomocą zmiennych pośrednich . $O(m^2)$

W przypadku drugiej części pytania, o ile mogę stwierdzić, każda wersja ZAKOŃCZENIA MAGICZNEGO KWADRATU powinna być NP-trudna, ale nie mam obniżek. Warto zauważyć, że istnieją procedury konstruowania normalnych magicznych kwadratów o dowolnie dużych rozmiarach; co więcej, liczba normalnych magicznych kwadratów wydaje się rosnąć superpolomicznie z (patrz OEIS A006052 ), więc podstawowy język nie wydaje się być rzadki. $n$

Korzystając z ograniczeń Papadimitriou w rozwiązaniach wystąpienia INTEGEROWEGO PROGRAMOWANIA LINIOWEGO, można również pokazać, że wersja, w której wszystkie liczby muszą być nieujemne, jest również w NP.

Twierdzenie (Papadimitriou) Niech być matrycy i o -wektor, zarówno w pozycji z . Następnie, jeśli ma rozwiązanie w liczbach całkowitych nieujemnych, ma również taki, w którym każdy składnik jest w . $A$ $r \times s$ $b$ $r$ $\{-a, -a+1, \dots, a-1, a\}$ $Ax = b$ $\{0,1,\dots,s(ra)^{2r+1}\}$

Wiązania tworzące magiczny kwadrat można wyrazić jako program liniowy za pomocą , ze zmiennymi i nierówności. Daje to nieco większą granicę niż granica powyżej, gdzie dozwolone są liczby ujemne, ale certyfikat wciąż ma wielkość wielomianową. (Podziękowania dla Tony Tan za wskazanie wyniku Papadimitriou.) $a=1$ $s=n^2+1$ $r=2n+2$

Christos H. Papadimitriou, O złożoności programowania liczb całkowitych , JACM 28 765–768, 1981. ( link )

— András Salamon
źródło

Chyba jestem zdezorientowany. jeśli wielkość odpowiedzi jest ograniczona, to gwarantujemy, że zgadniemy, że można odczytać i zweryfikować w czasie wielomianowym.

— Suresh Venkat

@Suresh: Przepraszamy za błędy, odpowiedź okazała się nieco trudniejsza do napisania niż się spodziewałem.

— András Salamon