Symmetric complementation

ABSTRACT

This paper introduces a class of 1 player games of perfect information, which we call complementing games;; the player is allowed moves which complement the value of successive plays. A complementing game is symmetric if all noncomplement moves are reversible (i.e., form a symmetric relation). These games are naturally related to a class of machines we call symmetric complementing machines. Symmetric nondeterministic machines were studied in [Lewis and Papadimitriou, 80]; they are identical to our symmetric complementing machines with complement moves allowed only on termination. (A companion paper to appear describes the computational complexity of symmetric complementing and alternating machines.) Of particular interest is the complexity class -&-Sgr;(@@@@) CSYMLOG, which contains the outcome problem of symmetric complementing games with constant complement bound with game positions encoded in log space, and next move relations computable in log space. We show that the decision problem for a restricted quantified Boolean logic -&-Sgr;(@@@@) QBF@@@@ is complete in -&-Sgr;(@@@@) CSYMLOG.

REFERENCES

• 1: Adleman, L., "Two theorems random polynomial time," 18th IEEE Symposium on Foundations of Computer Science, 75-83 (1978).
• 2: Aleliunas, R., R.M. Karp, R.H. Lipton, L. Lov-&-aacute;sz and C. Rackoff, "Random walks, universal traversal sequences, and complexity of maze problems," Proc. 20th Annual Symposium on Foundations of Computer Science, 218-223 (1979).
• 3: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 4: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 5: Cook, S.A., "Towards a complexity theory of synchronous parallel computation," Presented at Internationales Symposium -&-uuml;ber Logik und Algorithmik zu Ehren von Professor Hort Specker, Z-&-uuml;rich, Switzerland, February 1980.
• 6: Csanky, L., "Fast Parallel Matrix Inversion Algorithms," SIAM J. Comput. 5, 618-623 (1976).
• 7: Dymond, P. and S.A. Cook, "Hardware complexity and parallel computation," IEEE FOCS Conference, 1980.
• 8: Edmonds, J., "A combinatorial representation for polyhedral surfaces," Amer. Math. Soc. Notices7, 646 (1980).
• 9: S. Even , A. Pnueli , A. Lempel, Permutation Graphs and Transitive Graphs, Journal of the ACM (JACM), v.19 n.3, p.400-410, July 1972 [doi>10.1145/321707.321710]
• 10: Foldes, S. and P.L. Hammer, "Split graphs," 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing (F. Hoffman et al., eds.), Louisiana State Univ., Baton Rouge, Louisiana, 311-315 (1977).
• 11: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 12: Gill, J., "Complexity of probabilistic Turing machines," SIAM J. of Computing,6(4), 675-695 (1977).
• 13: Gilmore, P.C. and A.J. Hoffman, "A characterization of comparability graphs and of interval graphs," Canad. J. Math. 16, 539-548 MR31 #87 (1964).
• 14: Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]
• 15: D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
• 16: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 17: Hopcroft, J.E. and R.E. Tarjan, "Dividing a graph into triconnected components," SIAM J. Computing2:3 (1973).
• 18: Ja'Ja', J., and J. Simon, "Some space-efficient algorithms," Proc. 17th Allerton Conference, pp. 677-684, also Technical Report CS 80-23, Dept. Comp. Science, Penns. State Univ., Sept. 1980.
• 19: Ja'Ja', J., and J. Simon, "Parallel algorithms in graph theory: Planarity testing," Techn. Report CS-80-14, Penns. State Univ., June 1980.
• 20: Jones, N.D., Y.E. Lien, and W.T. Leaser, "New problems complete for nondeterministic log space," Math. System Theory 10, pp. 1-17 (1976).
• 21: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 22: Harry R. Lewis , Christos H. Papadimitriou, Symmetric Space-Bounded Computation (Extended Abstract), Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.374-384, July 14-18, 1980
• 23: McLane, S., "A combinatorial condition for planar graphs," Fundamenta Math. 28, 22-32 (1937).
• 24: McLane, S., "A structural characterization of planar combinatorial graphs," Duke Math. J. 3, 46-476 (1937).
• 25: Pnueli, A., A. Lempel, and S. Even, "Transitive orientation of graphs and identification of permutation graphs," Canad. J. Math. 23, 160-175 (1971).
• 26: Rabin, M.O., "Probabilistic algorithms," Algorithms and Complexity, New Directions and Recent Results, edited by J. Traub, Academic Press, 1974.
• 27: Reif, J.H., "On the power of probabilistic choice in synchronous parallel computations," Technical Report TR-30-81, Aiken Computation Lab., Harvard University, 1981.
• 28: Walter J. Savitch , Michael J. Stimson, Time Bounded Random Access Machines with Parallel Processing, Journal of the ACM (JACM), v.26 n.1, p.103-118, Jan. 1979 [doi>10.1145/322108.322119]
• 29: Schonhage, A., "Storage modification machines," Technical Report, Mathematisches Institut, Universit-&-auml;t T-&-uuml;bingen, Germany, 1979.
• 30: Tarjan, R.E., "Depth first search and linear graph algorithms," SIAM J. Computing1:2, 146-160 (1972).
• 31: White, A., Graphs, Groups and Surfaces, North-Holland Publishing Co., American Elsevier Co., New York, New York, 1973.
• 32: James Christopher Wyllie, The complexity of parallel computations, 1979