Symmetric Complementation. Revision
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, 801): they are identical to our symmetric complementing machines with complement moves allowed only on termination. (A companion paper to appear will describe the computational complexity of symmetric complementing and alternating machines.) Of particular interest is the complexity class Sum *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 Sum *QBF sum is complete in Sum *CSYMLOG. We also show that Sum *CSYMLOG contains many well- known and common combinatiorial problems: minimum spanning forests; k- connectivity and k-connected components, and also the recognition problems for many classes of graphs: planar graphs of valence 3; chordal graphs; comparability graphs; interval graphs; split graphs, and permutation graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1981
- Accession Number
- ADA108823
Entities
People
- John Reif
Organizations
- Harvard University