If parallel speedup requires exponentially many processors relative to input size, building a concrete computing device to implement such algorithms would be infeasible

\(\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