Złożoność n-królowych?

27

Klasyczne problemy z kolejką pytają, biorąc pod uwagę dodatnią liczbę całkowitą , czy istnieje tablica liczb całkowitych spełniająca następujące warunki: $n$ $n$ $Q[1..n]$

dla wszystkich $1\le Q[i] \le n$ $i$
dla wszystkich $Q[i] \ne Q[j]$ $i\ne j$
dla wszystkich $Q[i]-i \ne Q[j]-j$ $i\ne j$
dla wszystkich $Q[i]+i \ne Q[j]+j$ $i\ne j$

Każda liczba całkowita reprezentuje pozycję królowej w tym rzędzie szachownicy ; ograniczenia kodują wymóg, aby żadna królowa nie atakowała żadnej innej królowej. Łatwo jest udowodnić, że nie ma rozwiązań, gdy lub , a rozwiązania w postaci zamkniętej są znane dla wszystkich innych wartości . Tak więc, jako problem decyzyjny, problem queens jest całkowicie trywialny. $Q[i]$ $i$ $n\times n$ $n=2$ $n=3$ $n$ $n$

Standardowy algorytm cofania do konstruowania rozwiązania queens spekulacyjnie umieszcza królowe na prefiksie wierszy, a następnie rekurencyjnie określa, czy istnieje legalne umieszczenie królowych w pozostałych wierszach. Podproblem rekurencyjny można sformalizować w następujący sposób: $n$

Biorąc pod uwagę liczbę całkowitą i tablicę liczb całkowitych, czy jest przedrostkiem tablicy która opisuje rozwiązanie problemu kolejki? $n$ $P[1..k]$ $P$ $Q[1..n]$ $n$

Czy jest to bardziej ogólny problem decyzyjny NP-trudny?

Wiadomo, że kilka pobliskich pytań jest trudnych do NP, w tym uzupełnienie kwadratu łacińskiego [ Colbourn 1984 ], uzupełnienie Sudoku [ Yato i Seta 2002 ] oraz inne uogólnienie znaków tabens [ Martin 2007 ], ale wydaje się, że to konkretne pytanie umknęło jakakolwiek poważna uwaga. $n$

Powiązane pytania dotyczące cstheory.se:

cc.complexity-theory board-games

— Jeffε
źródło

2

Zastanawiam się, czy istniejące dowody kompletności NP w Sudoku, uzupełnienie kwadratu łacińskiego (i mnóstwo innych podobnych problemów) ... naprawdę dotyczą zwięzłych / rzadkich reprezentacji instancji (np. W dowodzie ukończenia łacińskiego kwadratu NPC, Colbourn mówi „Członkostwo w NP jest natychmiastowe”, ale nie wspomina o żadnym problemie z kodowaniem instancji).

— Marzio De Biasi,

1

@Marzio: te dowody są w dużym stopniu zależne od reprezentacji i (choć zwykle o tym nawet nie wspomniano) często nie jest nawet banalne ustanowienie członkostwa w NP, na przykład patrz cstheory.stackexchange.com/a/5559/109

— András Salamon

16

Minęły lata, ale ten post zainspirował nas do napisania artykułu, który ukazał się dzisiaj.

Odpowiedź jest taka, że n Queens Completion jest NP-Complete. Jednak do pełnego ujawnienia należy wspomnieć, że rozwiązujemy niewielki wariant problemu. W naszym przypadku zestaw królowych nie musi być przedrostkiem pełnego zestawu. Więc technicznie nie rozwiązaliśmy dokładnie zadanego tutaj problemu. Byłoby jednak niezwykle zaskakujące, gdyby wersja n Queens Completion z tego zapytania nie była również NP-Complete.

Chcę powtórzyć podziękowania, które włożyliśmy Jeffowi w artykuł za postawienie tego pytania tutaj.

Złożoność n Queens Completion Journal of AI Research Gent, Jefferson, Nightingale doi: 10.1613 / jair.5512 http://www.jair.org/papers/paper5512.html

— Ian Gent
źródło

Miły. Gratulacje!

— Jeffε

n - 1

$n-1$

n

$n$

6

(Wskazuje to na niektóre powiązane wyniki. Początkowo myślałem, że powiązane wyniki są bardzo powiązane, ale nie mogę szybko wypełnić luk, więc może wcale nie są tak powiązane. Być może nadal są pomocne.)

Ćwiczenie 118 w (szkic) sekcji 7.2.2.2 sztuki programowania komputerowego dotyczy bardzo podobnego problemu. W rozwiązaniu Knuth przypisuje artykuł, który z kolei uznaje

Gardnera, Gritzmannb, Prangenbergc, O złożoności obliczeniowej rekonstrukcji zestawów sieci z ich promieni rentgenowskich , 1999

$[2]=\{0,1\}$

$r,c\in[2]^m$ $a,b\in[2]^{2m-1}$

$x\in[2]^{m\times m}$ $\sum_j x_{ij}=r_i$ $\sum_i x_{ij}=c_j$ $\sum_i x_{i,s-i}=a_s$ $\sum_i x_{i,d+i}=b_{d+m-1}$

Nie jest dla mnie jasne, jak zredukować to do swojego problemu. Jednym spostrzeżeniem, które może pomóc, jest to, że wyjście twojego problemu zależy również tylko od sum, a nie od dokładnego umiejscowienia królowych. (Patrz Twierdzenie 2.4 w [Rivin, A Dynamic Programming Solution to the n-Queens Problem, 1992], chociaż być może jest to łatwe do zauważenia.)

Knuth udowadnia, że BINARNA TOMOGRAFIA CYFROWA jest kompletna z NP poprzez redukcję BINARNEGO PROBLEMU AWARYJNEGO. Jest to bardzo podobny problem, z wyjątkiem 3 wymiarów i bez przekątnych.

${xi},{xj},{xk}\in[2]^{n\times n}$

$x\in[2]^{n\times n\times n}$ $\sum_i x_{ijk}={xi}_{jk}$ $\sum_j x_{ijk}={xj}_{ik}$ $\sum_k x_{ijk}={xk}_{ij}$

Artykuł Gardnera i in. wydaje się redukować z bardziej standardowych problemów z kompletnym NP. Nie rozumiem wystarczająco dobrze żadnej redukcji, aby to wyjaśnić tutaj, więc zostawię wskaźniki z góry, abyś mógł je zbadać, jeśli chcesz.

To wszystko może być bezużyteczne, chyba że ktoś wymyśli, jak zredukować BINARNĄ TOMOGRAFIĘ CYFROWĄ do zadanego pytania.

— Radu GRIGore
źródło