has chosen which bulbs to light, is an NP-hard problem. However, there is a polynomial-time approximation scheme for the game that can find a choice for the second player that leaves only times the minimum possible number of lit bulbs, for any , in time . Connection to coding theory The Berlekamp switching game can be used in coding theory as a demonstration of the covering radius of a certain binary linear code. A binary linear code of length and dimension is defined as a -dimensional linear subspace of the -dimensional vector space over the finite field with two elements, . The elements of the subspace are called codewords, and the covering radius is the smallest number such that every point of is within Hamming distance of a codeword. Let and . For these parameter values, the vector space describes all possible patterns of lit bulbs on the array of lightbulbs, with a vector addition operation that combines two patterns by lighting the bulbs that appear in exactly one of the two patterns (the symmetric difference operation on the sets of lit bulbs). One can define a linear subspace consisting of all patterns that the second player can turn completely off, or equivalently of all patterns that the second player could create starting with a board that is completely off. Although the second player has choices for how to set the second bank of switches, this subspace has elements, giving it dimension , because flipping all of the second player's switches has no effect on the pattern of lit bulbs. Then is the covering radius of this code. The set of lit bulbs chosen by the first player, with best play, gives a point of that is as far as possible from the linear subspace. The set of bulbs whose state is changed by the second player, with best play, gives the closest point in the linear subspace. The set of bulbs that remain lit after these choices are the ones whose number defines the Hamming distance between these two points. See also Lights Out (game), a different puzzle involving turning off lightbulbs using switches that control multiple bulbs References Coding theory Mathematical games