5. The hierarchy of complexity classes 45

replies with b1, then W says w2, etc. Each string has length polynomial in

|x|. Each player is allowed to see the strings already chosen by his opponent.

The game is completed after some prescribed number of steps, and

the referee, who knows x and all the strings and who acts according to

a polynomial-time algorithm, declares the winner. In other words, there is a

predicate W (x, w1,b1,w2,b2,... ) that is true when W is the winner, and we

assume that this predicate belongs to P. If this predicate is false, B is the

winner (there are no ties). This predicate (together with polynomial bounds

for the length of strings and the number of steps) determines the game.

Let us note that in fact the termination rule can be more complicated,

but we always assume that the number of moves is bounded by a polynomial.

Therefore we can “pad” the game with dummy moves that are ignored by

the referee and consider only games where the number of moves is known in

advance and is a polynomial in the input length.

Since this game is finite and has no ties, for each x either B or W has

a winning strategy. (One can formally prove this using induction over the

number of moves.) Therefore, any game determines two complementary

sets,

Lw = {x: W has a winning strategy} ,

Lb = {x: B has a winning strategy} .

Many complexity classes can be defined as classes formed by the sets Lw (or

Lb) for some classes of games. Let us give several examples.

P: the sets Lw (or Lb) for games of zero length (the referee declares the

winner after he sees the input)

NP: the sets Lw for games that are finished after W’s first move. In

other words, NP-sets are sets of the form

{x : ∃ w1W (x, w1)}.

co-NP: the sets Lb for games that are finished after W’s first move. In

other words, co-NP-sets are sets of the form

{x : ∀ w1 B(x, w1)}

(here B = ¬W means that B wins the game.)

Σ2: the sets Lw for games where W and B make one move each and then

the referee declares the winner. In other words, Σ2-sets are sets of the form

{x : ∃ w1 ∀ b1 W (x, w1,b1)}.

(W can make a winning move w1 after which any move b1 of B makes B

lose).