##
**Two applications of inductive counting for complementation problems.**
*(English)*
Zbl 0678.68031

Summary: Following the recent independent proofs of N. Immerman [SIAM J. Comput., 17, 935-938 (1988)] and R. Szelepcsényi [Bull. EATCS 33, 96-100 (1987; Zbl 0664.68082)] that nondeterministic space-bounded complexity classes are closed under complementation, two further applications of the inductive counting technique are developed. First, an errorless probabilistic algorithm for the undirected graph s-t connectivity problem that runs in 0(log n) space and polynomial expected time is given. Then it is shown that the class LOGCFL is closed under complementation. The latter is a special case of a general result that shows closure under complementation of classes defined by semi-unbounded fan-in circuits (or, equivalently, nondeterministic auxiliary pushdown automata or tree-size bounded alternating Turing machines). As one consequence, it is shown that small numbers of “role switches” in two- person pebbling can be eliminated.

### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68Q45 | Formal languages and automata |

68R10 | Graph theory (including graph drawing) in computer science |

60G50 | Sums of independent random variables; random walks |

94C99 | Circuits, networks |

03D55 | Hierarchies of computability and definability |

91A05 | 2-person games |