Czy problem N Queens jest trudny NP?

Problem N-królowej jest następujący:

Wejście: N

Wynik: umieszczenie N „królowych” na szachownicy NXN w taki sposób, że żadne dwie królowe nie leżą w tym samym rzędzie, kolumnie lub po przekątnej.

Przeszukując to w Google, zauważyłem, że wiele slajdów wielu profesorów twierdzi, że jest to trudny problem NP (np. Web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

Jednak nie udało mi się znaleźć dowodu (ani go uzyskać). Powodem, dla którego zadaję to pytanie, jest to, że myślę, że mam algorytm, który rozwiązuje pewne przypadki problemu, tj. Gdy N nie jest wielokrotnością 2 lub 3 (N to liczba królowych). Powiązany problem - czy możemy uznać rozmiar wejściowy za N (gdzie N jest liczbą królowych)? Czy też przyjmujemy wielkość wejściową jako log (N), ponieważ liczbę „N” można przedstawić w bitach log (N)?

cc.complexity-theory np-hardness csp Anshul Singhle
źródło

(1) Dlaczego używasz zarówno N, jak i n? Czy są to te same zmienne, czy różne zmienne? (2) Dla każdej liczby całkowitej n oprócz 2 i 3 istnieje sposób na umieszczenie n królowych na planszy n × n spełniających warunek n-królowej (patrz Wikipedia ), więc nie wiem o jakim problemie mówisz, kiedy mówicie „to trudny problem NP”.

Tsuyoshi Ito

Pamiętam, że występuje wynik twardości, gdy płyta niekoniecznie jest kwadratowa: tzn. Kształt deski jest podany jako część danych wejściowych.

Sasho Nikolov

n \times n

$n \times n$

n

$n$

Być może liczenie rozwiązań jest nieco bardziej interesującym problemem (poza klasą #P, jak udowodniono w „Trudnościach liczenia problemów z kompletnymi mapowaniami”).

Marzio De Biasi,

Zobacz także: dl.acm.org/citation.cfm?id=122322

Jeffε

Odpowiedzi:

Jak stwierdzono, odpowiedź na to pytanie brzmi NIE.

Odnośniki: Wielomianowy algorytm czasu http://dl.acm.org/citation.cfm?id=101343 [dzięki uprzejmości: vzn]

Kolejna znacznie prostsza technika: http://dl.acm.org/citation.cfm?id=122322 [dzięki uprzejmości: Jeffe]

Anshul Singhle
źródło

możesz rozważyć przyjęcie tej odpowiedzi, aby nie pojawiała się ponownie jako odpowiedź.

Suresh Venkat,

Algorytm czasu wielomianowego w pierwszym odwołaniu nie gwarantuje rozwiązania. To, czy algorytm się powiedzie, czy nie, zależy od początkowej konfiguracji, która jest wybierana losowo, a autorzy dają tylko empiryczne dowody, że wydaje się, że potrzeba wielomianowej liczby prób, dopóki się nie powiedzie.

Tsuyoshi Ito,

Drugie odniesienie też nie jest dowodem. To, że znaleziono jedno możliwe rozwiązanie dla n-królowych o n = 500000, nie oznacza, że jest w P. (To tylko zwiększa prawdopodobieństwo)

Geoffrey De Smet

W rzeczywistości okazało się, że tak właśnie jest.

https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/ ]

Kasper
źródło

N

$N$

@ClementC. W rzeczywistości, ponieważ pierwotne pytanie nie jest wystarczająco precyzyjne, myślę, że Kasper ma rację, nawet jeśli jego sposób wyrażenia jest niepełny. Decydując, biorąc pod uwagę n, czy istnieje umiejscowienie, jest wyraźnie w P, ponieważ problem zawsze ma rozwiązania dla n> 3. Zatem problem z ukończeniem n-królowych (decydowanie, czy można rozszerzyć dane częściowe rozwiązanie) wydaje się naturalnym problemem decyzyjnym, aby przyjrzeć się złożoności problemu.

holf

@holf To rzeczywiście ważny punkt Państwo zrobić, ale że ta odpowiedź nawet nie wspominając (a czytelnik będzie absolutnie nie dostać czytając to). Posiadanie mylącej odpowiedzi na dwuznaczne pytanie nie jest do końca optymalne.

Klemens C.