Some combinatorial game problems require Ω( n k ) time
Akeo Adachi, Shigeki Iwata, Takumi Kasai · Journal of the ACM · 1984
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.