Concepedia

The Othello game on an n × n board is PSPACE-complete

Shigeki Iwata, Takumi Kasai

Theoretical Computer Science · 1994 · 78 citations · 10 references

DOI

Concepts

References

10

Alternation

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer · Journal of the ACM · 1981 · 1.2K citations · Full text

, , +17

Planar Formulae and Their Uses

David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations

, , +13

On the complexity of some two-person perfect-information games

Thomas J. Schaefer · Journal of Computer and System Sciences · 1978 · 312 citations

, , +12

Computing a perfect strategy for n × n chess requires time exponential in n

Aviezri S. Fraenkel, David Lichtenstein · Journal of Combinatorial Theory Series A · 1981 · 184 citations

, , +11

GO Is Polynomial-Space Hard

David Lichtenstein, Michael Sipser · Journal of the ACM · 1980 · 182 citations · Full text

, , +10