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?