Complexity of decision problems based on finite two-person perfect-information games

ABSTRACT

We present a number of simply-structured combinatorial games for which the problem of determining the outcome of optimal play is complete in polynomial space—a condition which gives very strong assurance that these problems are hard. In addition to proving this completeness property for some particular games, we introduce a general technique for deriving games complete in polynomial space from NP-complete problems.

REFERENCES

• 1: Bauer, M., Brand, D., Fischer, M., Meyer, A. and Paterson, M. A note on disjunctive form tautologies. SIGACT News April 1973, 17-20.
• 2: Berlekamp, E.R. L-R Hackenbush is NP Complete. rough preliminary draft, April 1975.
• 3: Shimon Even , R. Endre Tarjan, A combinatorial problem which is complete in polynomial space, Proceedings of seventh annual ACM symposium on Theory of computing, p.66-71, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803754]
• 4: Guy, R.K. and Smith, C.A.B. The G-Values of Various Games. Cambridge Philosophical Society Proceedings vol. 52 (1956) 514-526.
• 5: Karp, R.M. Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher eds., Plenum Press (1972) 85-104.
• 6: Meyer, A.R. and Stockmeyer, L.J. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. 13th Annual IEEE Symposium on Switching and Automata Theory (1972) 125-129.
• 7: Stockmeyer, L.J. The Polynomial-Time Hierarchy. IBM Research Report RC 5379. (April 1975)
• 8: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory