Symmetric complementation

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 Σ∗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 Σ∗QBF⊕ is complete in Σ∗CSYMLOG. We also show that Σ∗CSYMLOG contains many well-known and common combinatorial problems: (1) minimum spanning forests (2) k-connectivity and k-connected components and also the recognition problems for many classes of graphs: (3) planar graphs of constant valence (4) chordal graphs (5) comparability graphs (6) interval graphs (7) split graphs (8) permutation graphs. Ke present a probabilistic algorithm (this is an algorithm which makes probabilistic choices [Rabin, 74], but with no assumptions about the probability distribution of the inputs) for recognizing the languages of Σ∗CSYMLOG within space O(log(n)) and simultaneous time nO(1), with error probability <ϵ for any given ϵ, 0<ϵ<1. As a consequence, problems (1)-(8) can be done probabilistically in space O(log(n)) and within simultaneous polynomial time. The best previous known algorithms for problems (1), (2) and (3) required deterministic space ω(log2n) [Ja'Ja' and Simon, 79], and algorithms for problems (4)-(8) previously required space Ω(n). Also, we give a probabilistic parallel algorithm (which employs the Hardware Modification Machines of [Cook, 80], with probabilistic choice) for recognizing the languages of Σ∗CSYMLOG within parallel time O(log n) and error probability <ϵ, for any given ϵ, 0<ϵ<1. Thus we also have parallel time O(log n) algorithms for problems (1)-(8). Our parallel algorithms seem practical since they require only a small polynomial number of processors. The best previously known parallel algorithms for problems (1)-(3) required parallel time Ω(log2n) [Ja'Ja' and Simon, 80] and we know of no previous parallel algorithms for problems (4)-(8). Furthermore, we show (by a nonconstruct-ive technique) that for each input length n≥0, the probabilistic choice can be eliminated in both our sequential and parallel algorithms. This does not affect the efficiency of the algorithms, but makes our algorithms nonuniform (i.e., we have a different algorithm for each input length).

Duke Scholars

Author John H. Reif Computer Science