The first "natural" languages are established as solvable m deterministic polynomial time, for the recogmtion of which polynomial-time lower bounds can be shown.The k-pebble game problem Is to determine whether the first player has a forced win in the pebble game using only k pebbles.The main result of this paper is that the k-pebble game problem requires ft(n (~-~)/4-') time for its recogmUon on multitape Tunng machines for any ~ > 0. The problem is solvable m deterministic polynomial time.Then we consider other combinatorial game problems that also have nontrivlal polynomial deterministic lower time bounds.

There have been numerous attempts to discuss the time complexity of problems and classify them into hierarchical classes such as P, NP, PSPACE, EXP, etc. A great number of familiar problems have been reported which are complete in NP (nondeterministic polynomial time). Even and Tarjan considered generalized Hex and showed that the problem to determine who wins the game if each player plays perfectly is complete in polynomial space. Shaefer derived some two-person game from NP complete problems which are complete in polynomial space. A rough discussion such as to determine whether or not a given problem belongs to NP is independent of the machine model and the way of defining the size of problems, since any of the commonly used machine models can be simulated by any other with a polynomial loss in running time and by no matter what criteria the size is defined, they differ from each other by polynomial order. However, in precise discussion, for example, in the discussion whether the computation of a problem requires O(n k) time or O(nk+l) time, the complexity heavily depends on machine models and the definition of size of problems. From these points, we introduce somewhat stronger notion of the reducibility.

A “pebble game” is introduced and some restricted pebble games are considered. It is shown that in each of these games the problem to determine whether there is a winning strategy (two-person game) is harder than the solvability problem (one-person game). We also show that each of these problems is complete in well-known complexity classes. Several familiar games are presented whose winning strategy problems are complete in exponential time.