This is a restatement of an earlier question.Consider the following impartial perfect information game between two players, Alice and Bob.  The players are given a permutation of the integers 1 through n.  At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player.  Alice plays first.  For example:(1,2,3,4)  Bob wins immediately, by definition.(4,3,2,1)  Alice wins after three turns, no matter how anyone plays.(2,4,1,3)  Bob can win on his first turn, no matter how Alice plays.(1,3,2,4)  Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.(1,4,3,2)  Alice eventually wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by not removing the 1.Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming perfect play?  More generally, because this is a standard impartial game, every permutation has a SpragueGrundy value; for example, (1,2,4,3) has value *1 and (1,3,2) has value *2.  How hard is it to compute this value?The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.
Permutation game redux
gt.game theory;combinatorial game theory