Akeo Adachi

TCS Journal 2000 Journal Article

Complexity of path discovery game problems

• Hiroaki Tohyama
• Akeo Adachi

In this paper path discovery games are introduced, and complexity of the game problems is studied. It is shown that the path discovery game problem played on directed graphs is PSPACE-complete, and the path discovery game problem played on undirected graphs is in the class SSPACE (nlogn). Moreover, it is shown that the acyclic path discovery game problems played on directed graphs and on undirected graphs are both NP-complete.

STOC Conference 1981 Conference Paper

Low Level Complexity for Combinatorial Games

• Akeo Adachi
• Shigeki Iwata
• Takumi Kasai

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.

MFCS Conference 1979 Conference Paper

A Theoretical Study of the Time Analysis of Programs

• Akeo Adachi
• Takumi Kasai
• Etsuro Moriya