game independently, some time prior to 1971. Early research on related problems included publications by , whose computer experiments can be interpreted as asking, for the game, how well the second player can do against a first player who plays randomly, and by , who address Gleason's question theoretically, showing that for almost all choices of the first player, in the limit of large game board sizes, the optimal game value is close to . Analysis Mathematically, one can describe the lights turned on by the first player's move as a set , and the smallest number of lights that can be achieved by the best play for the second player as a number . The best play for the first player is to choose a set that maximizes . Therefore, one can describe the largest number of lights that can be achieved by the best play for the first player as a number . Beyond the question of how to play well in an individual game, a broader question that has been the object of mathematical research is to characterize the value of in general, as a function of and , to determine its behavior as a function, or to calculate its value for as many combinations of and as possible. The case of a square array has been solved for . Additionally, lower bounds for have been found for . These numbers are: Asymptotically, these numbers grow as . Computational complexity Because there are exponentially many choices for which switches to flip, an exhaustive search for the optimal choice is not possible for large , setting up the question of how well computationally-limited players can play this game. The first player can cause the expected game value to be by playing randomly. Similarly, the second player can obtain a value whose expected distance from is by playing randomly; this value might either be larger or smaller than , but if it is larger the second player can flip all row switches to get a value that is smaller by the same amount. This random strategy for the second player can be made non-random using the method of conditional probabilities, giving a polynomial time algorithm that obtains the same solution value guarantees. A different derandomization gives a parallel algorithm in the complexity class NC. Finding the optimal choice for the second player in the game, once the first player