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).
Previous Page Next Page