SIAM Journal on Computing · 1989 · 135 citations · 28 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationCircuit ComplexityComputational ComplexityComputational Complexity ClassesAlternating Turing MachinesComplexity ClassesCounting Complexity ClassesImmerman-szelepcsényi TheoremNondeterministic ComplexityNondeterministic Pushdown AutomataNondeterministic Space ComplexityNondeterministic Turing Machines
Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] 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 $O(\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.
28
PE, P. Billingsley · Journal of the American Statistical Association · 1996 · 6.7K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
Stephen Warshall · Journal of the ACM · 1962 · 1.7K citations
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer · Journal of the ACM · 1981 · 1.2K citations · Full text