MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

No, not the war on drugs, but the game of War considered in http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length As noted in that discussion, the game of war can go on forever, but my question is: can it be decided in polynomial time whether a given configuration leads to a periodic or a finite game (the question is decidable, since you can just look at a sequence of $n n!$ moves (where $n$ is the initial number of cards), but $n n!$ is not so small.)
EDIT To answer Joel's very good question: the setup is: the two adversaries have decks $A$ and $B,$ both face down. they flip their top cards, call them $a_1$ and $b_1.$ If $v(a_1) > v(b_1)$ ($v()$ is the value), we put $a_1$ on top of $b_1,$ turn the stack of two cards upside down and add them to the bottom of $A$'s deck (and similarly if $v(b_1) > v(b_k).$ If $v(a_1) = v(b_1)$ we flip two more cards $a_2, b_2$ put them on top of $a_1, b_1$ respectively. If $v(a_2) > v(b_2)$ we put the stack of $a$s on top of the stack of $b$s, flip the resulting $4$-stack upside down, and add it to the bottom of the $A$ stack. If $v(a_2) = v(b_2)$ we continue as before. If we keep getting equal values, and one of the players runs out of cards, the other player wins. If both players run out of cards simultaneously, the game is declared a draw.
No, not the war on drugs, but the game of War considered in http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length As noted in that discussion, the game of war can go on forever, but my question is: can it be decided in polynomial time whether a given configuration leads to a periodic or a finite game (the question is decidable, since you can just look at a sequence of $n n!$ moves (where $n$ is the initial number of cards), but $n n!$ is not so small.)