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

Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzo, Walter L.; Tompa, Martin

SIAM J. Comput. 18, No. 3, 559-578 (1989).

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

Keywords:

symmetric computation; random walk; NC; semi-unboundedness; hierarchy; inductive counting; complementation; probabilistic algorithm; connectivity; LOGCFL; pebbling

Citations:

Zbl 0664.68082