The difficulty of deciding TWO PLAYER SAT_n parallels the difficulty of deciding winning strategies in increasingly long games

\(\sc{TWO}\ \sc{PLAYER}\ \sc{SAT}_n\) may be shown to be complete for the class \(\Sigma^P_n\) in the Polynomial Hierarchy. Note, however, as the value of \(n\) increases, we expect that it should become more difficult to decide membership in \(\sc{TWO}\ \sc{PLAYER}\ \sc{SAT}_n\) in much the same way that it appears to become more difficult to determine whether a given player has a winning strategy for increasingly long games of Go or chess. This observation provides part of the reason why it is