A Combinatorial Problem Which Is Complete in Polynomial Space

ABSTRACT

This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem solvable in polynomial space is solvable in polynomial time. This result suggests that the theory of combinational games is difficult.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BRuNo, J, AND WEINaERO, L A construcUve graph-theoretic soluuon of the Shannon switching game IEEE Trans on Clrcutt Theory CT-17, 1 (Feb. 1970), 74-81
• 3: CHASE, S An implemented graph algon~m for winning Shannon switching games. Tech. Rep RC-3121, IBM Thomas T Watson Research Center, Yorktown Heights, N Y, 1970
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: KARP, R Reduclblhty among combinatorial problems In Complextty of Computer Computanons, R E Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-104.
• 6: 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]
• 7: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 8: Thomas J. Schaefer, Complexity of decision problems based on finite two-person perfect-information games, Proceedings of the eighth annual ACM symposium on Theory of computing, p.41-49, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803629]
• 9: TA~AN, R Depth-first search and hnear graph algorithms. SlAM J Computing 1,2 (1972), 146-160
• 10: TARJAN, R Unpublished notes (1974)

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Performance, Theory