patternMinor
Could this be an NP-Complete problem?
Viewed 0 times
thisproblemcompletecould
Problem
Consider the following problem statement:
Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins.
For example:
Initial State: 37
Player1 subtracts 16. State: 21
Player2 subtracts 8. State: 13
Player1 subtracts 4. State: 9
Player2 subtracts 9. State: 0
Player2 wins!
Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.
This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length n (where n is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).
Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?
Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins.
For example:
Initial State: 37
Player1 subtracts 16. State: 21
Player2 subtracts 8. State: 13
Player1 subtracts 4. State: 9
Player2 subtracts 9. State: 0
Player2 wins!
Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.
This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length n (where n is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).
Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?
Solution
The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.
Context
StackExchange Computer Science Q#70538, answer score: 6
Revisions (0)
No revisions yet.