Czy może to być problem z NP-Complete?

10

Rozważ następujące stwierdzenie problemu:

Biorąc pod uwagę początkową liczbę, ty i twój przyjaciel na zmianę odejmujemy od niej idealny kwadrat. Pierwszy, który osiągnie zero, wygrywa. Na przykład:

Stan początkowy: 37

Gracz 1 odejmuje 16. Stan: 21

Gracz 2 odejmuje 8. Stan: 13

Gracz 1 odejmuje 4. Stan: 9

Gracz 2 odejmuje 9. Stan: 0

Gracz 2 wygrywa!

Napisz program, który ma stan początkowy, zwraca optymalny ruch, tj. Taki, który z pewnością doprowadzi do wygrania gry. Jeśli żaden możliwy ruch nie może doprowadzić cię do zwycięskiego stanu, zwróć -1.

Problem ten można rozwiązać w czasie pseudo-wielomianowym za pomocą programowania dynamicznego. Ideą jest po prostu wypełnienie tablicy o długości n (gdzie n jest stanem początkowym) optymalnymi ruchami lub -1, jeśli żaden ruch nie prowadzi do wygranej. To zajęłoby O (n * sqrt (n)), ponieważ dla każdej liczby należy rozważyć odjęcie każdego możliwego idealnego kwadratu mniejszego od niego (jest ich ~ sqrt (n)). Jest to jednak pseudo-wielomianowa złożoność środowiska wykonawczego, ponieważ środowisko wykonawcze faktycznie skaluje się wykładniczo w stosunku do wielkości danych wejściowych w formacie binarnym (liczba bitów użyta do przedstawienia liczby).

Czy ktoś może pomyśleć o algorytmie wielomianowym do rozwiązania tego problemu? Jeśli nie, czy może to być NP-Complete? Dlaczego?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Martin Copes
źródło
1
Z ciekawości dlaczego pytasz konkretnie, czy jest kompletny z NP? (Osobiście
zgadłbym
@ruakh Ostatnio napotkałem ten problem podczas wywiadu z kodowaniem i zaproponowałem rozwiązanie pseudo-wielomianowe przy użyciu programowania dynamicznego, które opisałem. Jednak po dokładnym przemyśleniu problemu nie mogłem wymyślić algorytmu wielomianowego czasu. Wkrótce zacząłem zadawać sobie pytanie, czy to nie był problem NP (-Complete).
Martin Copes
Czy próbowałeś obliczyć, które pozycje wygrywają, a które tracą? Być może powstanie wzór.
Yuval Filmus
@YuvalFilmus Według Wikipedii nie ma znanej formuły dla tego wzoru (sekwencja A030193 w OEIS)
Martin Copes
Właśnie, właśnie zamierzałem opublikować odpowiedź z tymi informacjami. Zobacz także A224839.
Yuval Filmus

Odpowiedzi:

6

Sekwencję pozycji tracących można znaleźć w OEIS, A030193 , podobnie jak sekwencję pozycji mających wartość Grundy 1, A224839 . Encyklopedia cytuje kilka istotnych artykułów. Być może niektóre z nich omawiają nietrywialne algorytmy obliczania sekwencji.

Yuval Filmus
źródło
Jak wspomniałeś, sekwencja ta przedstawia pozycje tracące. Nawet jeśli byłeś w stanie sprawdzić na bieżąco, czy pozycja traci, czy nie (co wydaje się trudne!) Problem wciąż prosi o powrót optymalnego ruchu, tj. Jaki kwadrat należy odjąć do bieżącego stanu, aby dostać się do pozycja przegrana. Problem sprowadzałby się do znalezienia pozycji tracącej przez odjęcie kwadratów od aktualnego stanu. Wciąż musisz iterować wszystkie kwadraty mniejsze niż stan, nawet jeśli możesz sprawdzić, czy pozycja traci w stałym czasie.
Martin Copes
3
Racja, to nie wystarczy, ale będzie dobry początek. Być może zyskasz wgląd w możliwość obliczenia tylko zwycięskiego statusu pozycji. Dodatkowo, pokazanie, że trudno jest zdecydować, która pozycja traci, wystarczy, aby pokazać, że twój problem, jak stwierdzono, jest trudny NP, w każdej rozsądnej wersji decyzji.
Yuval Filmus