Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?

Czy następujący problem jest trudny NP?

Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.$n\times n$

Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym. Istnieją trzy główne różnice między tymi dwiema grami.$n\times n$

Pierwszą i najbardziej znaczącą różnicą jest zasada „latającego króla”. W warcabach król może przeskoczyć kawałek sąsiadującego przeciwnika na puste pole dwa kroki dalej w dowolnym kierunku po przekątnej. W przeciągach międzynarodowych król może przeskoczyć kawałek przeciwnika na dowolną odległość, przesuwając dowolną odległość wzdłuż przekątnej.

Podobnie jak w warcabach, ten sam element można wykorzystać do przechwycenia serii elementów w jednej turze. Jednak w przeciwieństwie do warcabów, przechwycone elementy w przeciągach międzynarodowych nie są usuwane, dopóki cała sekwencja się nie skończy. Kawałek przechwytujący może kilkakrotnie przeskoczyć lub wylądować na tym samym pustym polu, ale nie może przeskoczyć pionka przeciwnika więcej niż raz.

Wreszcie, zarówno warcaby, jak i projekty międzynarodowe mają zasadę wymuszonego przejęcia: jeśli możesz schwytać kawałek przeciwnika, musisz. Jednak reguły reguł nie zgadzają się, gdy istnieje kilka opcji dla wielu. W warcabach możesz wybrać dowolną maksymalną sekwencję przechwytywania; innymi słowy, możesz wybrać dowolną sekwencję przechwytywania, która kończy się, gdy przechwytujący element nie może już przechwycić. W projektach międzynarodowych musisz wybrać najdłuższą sekwencję przechwytywania. Zatem mój problem jest równoważny z następującym:

Biorąc pod uwagę konfigurację planszy dla międzynarodowych przeciągów , znajdź ruch, który uchwyci maksymalną liczbę przeciwnych pionków.$n\times n$

Wystarczy udowodnić, że następujący problem jest NP-zupełny. (Jest oczywiście w NP.)

Biorąc pod uwagę konfigurację planszową dla międzynarodowych draftu, w których biorą udział tylko królowie , czy (i dlatego musi) jeden gracz może przechwycić wszystkie elementy przeciwnika w jednej turze?$n\times n$

Odpowiedzi na problem warcabów można rozwiązać w czasie wielomianowym; to zabawne zadanie domowe. Problem wygląda bardziej podobnie do analizy końcowych gier Phutball Demaine, Demaine i Eppstein ; rozwiązanie zabawnej pracy domowej pojawia się na końcu ich artykułu. Rozwiązanie pojawia się również w pracy FOCS 1978 autorstwa Frankela i in. dowodzi to, że optymalne granie w warcaby jest trudne dla PSPACE; zobacz także dowód Robsona z 1984 r., że warcaby są w rzeczywistości DODATKOWE.

OK, oto redukcja. Okazuje się, że mimo wszystko nie potrzebujesz płaskości. Ponadto, jeśli chodzi o „znaleźć legalny ruch”, zadaję pytanie, ponieważ „czy ruch X jest legalny?”.

Najpierw pracujmy zamiast tego w grze, w której pionki poruszają się prostopadle zamiast po przekątnej. Ta gra jest równoważna (wystarczy spojrzeć na planszę obróconą o 45 stopni), z wyjątkiem właściwości krawędzi, których nie będziemy używać. Używamy dwóch gadżetów: scalania / podziału i podziału. Zobacz http://www.hearn.to/draughts.pdf . Zakładamy, że na planszy jest jeden Biały Król do ruchu. (Żaden inny element nie będzie w stanie uchwycić żadnej znaczącej liczby elementów.) Porusza się przez wskazane korytarze, przechwytując czarne kawałki po drodze.

Najpierw połącz: jeśli król wejdzie na którąkolwiek z N ścieżek A (przechwytując czarny kawałek, nie pokazano), może wyjść w B. Podobnie, jeśli odwrócimy gadżet i wejdzie on w B, przechwytując pokazany kawałek, może opuścić dowolną ścieżkę A (ponownie, chwytając zewnętrzny czarny kawałek). Jest to gadżet jednorazowego użytku (ponieważ czarny kawałek wyjścia można uchwycić tylko raz).

Po drugie, zwrotnica. Jeśli król wejdzie przez A (C), może wyjść w B (D). Nie może zatrzymać się na środku i zmieniać tras, ponieważ byłby to nieuchwytny segment ruchu.

Teraz, mając skierowany wykres, skonstruuj odpowiednią konfigurację gry w następujący sposób. Dla każdego wierzchołka stwórz scalenie, które zasila się na podział. Kieruj podzielone wyjścia do danych wejściowych scalania gadżetów wierzchołków (scalanie + podział) odpowiadających wierzchołkom, z którymi wychodzące krawędzie łączą się, używając w razie potrzeby zwrotnic. Rozpocznij króla od dodatkowego wejścia do dowolnego wierzchołka (z czarnym kawałkiem do przechwycenia, aby mógł wejść do wierzchołka).

Na koniec wyrównaj wszystkie „długości krawędzi”, dodając w razie potrzeby dodatkowe czarne elementy wzdłuż ścieżek wyjściowych / wejściowych. Jeśli są V wierzchołki i k czarnych kawałków wzdłuż każdej krawędzi, król może przechwycić 2 V + kV + 1 sztuk, tylko wtedy, gdy istnieje obwód hamiltonowski na odpowiednim wykresie. Jeśli król ma dostępny ruch alternatywny, przechwycenie prostego łańcucha elementów 2 V + kV, a następnie ustalenie, czy ten ruch alternatywny jest legalny, jest NP-zakończone.

Oto możliwa alternatywa dla redukcji Boba, tym razem z (nieukierowanego) cyklu hamiltonowskiego. Nie jestem w 100% pewien, że szczegóły są poprawne - już znalazłem i naprawiłem kilka problemów - ale jestem pewien, że można je wmasować we właściwy dowód. Jak podkreśla Bob, ta redukcja ma poważny błąd; biały król może łatwo zejść ze swojej kanonicznej ścieżki przez planszę. Ten błąd można naprawić, dodając gadżet crossovera Boba w odpowiednich lokalizacjach (tak myślę) , ale nie różni się on znacznie od jego redukcji.

Niech będzie niekierowanym wykresem z wierzchołkami i krawędziami . Narysuj w płaszczyźnie, umieszczając jej wierzchołki w regularnie rozmieszczonych punktach na linii o nachyleniu i rysując każdą krawędź jako odcinek poziomy plus odcinek pionowy, oba powyżej linii wierzchołków.n m G - $G$$n$$m$$G$$-1$

Teraz zmniejszamy ten rysunek do planszy (obróconej o 45 stopni) z czarnymi szachownicami i jednym białym królem. Potrzebujemy trzech rodzajów gadżetów: narożników, rozgałęźników i hord. Narożnik zawiera dwa czarne elementy, które można schwytać razem, zmieniając kierunek białego króla. -splitter zawiera pojedynczy element, który musi być zrobione w określonym kierunku, z miejsc szczególnych dla króla przechwytywania wskoczyć. Wreszcie, skarb to duża skrzynia pełna czarnych kawałków, które muszą być schwytane w określonej kolejności, dla pewnej dużej stałej . Na poniższych rysunkach szare koła są elementami, których nie można uchwycić.O ( n 2 + m ) k k h n $O(n^2)\times O(n^2)$$O(n^2+m)$$k$$k$$hn$$h$

Teraz zamień każdy wierzchołek stopnia na skarb, podłączony do poziomego rozdzielacza i pionowego rozdzielacza. Dla każdej krawędzi umieść stałą liczbę narożników wyrównanych z rozdzielaczami dla skarbu i skarbu . Jest to łatwe przygotowanie rogach dla różnych krawędziach leżeć pod różnymi - i -coordinates. Umieść białego króla w jednym ze skarbów, w pozycji pokazanej przez biały okrąg powyżej.k k ( i , j ) i j x $k$$k$$k$$(i,j)$$i$$j$$x$$y$

Biały król może schwytać co najmniej przeciwległych elementów - każdy element w każdym skarbie plus cztery dodatkowe elementy krawędzi na wierzchołek - tylko wtedy, gdy wykres jest hamiltonianem.$hn^2+4n$$G$

Dlaczego nie przedstawiłeś mi tego problemu, kiedy pracowałem nad moją pracą magisterską?

OK, mam redukcję z Planarskiego cyklu Hamiltonianowskiego.