Low Level Complexity for Combinatorial Games

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.

Authors

• Akeo Adachi
• Shigeki Iwata
• Takumi Kasai

Keywords

No keywords are indexed for this paper.