Two Applications of Inductive Counting for Complementation Problems

DOI10.1137/0218038zbMath0678.68031OpenAlexW2071260871WikidataQ29542907 ScholiaQ29542907MaRDI QIDQ3835019

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

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218038

zbMATH Keywords

connectivityrandom walkcomplementationprobabilistic algorithmhierarchyLOGCFLpebblingNCsemi-unboundednessinductive countingsymmetric computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) 2-person games (91A05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Circuits, networks (94C99) Hierarchies of computability and definability (03D55)

Related Items (max. 100)

Equivalence classes and conditional hardness in massively parallel computations ⋮ \(\text{RL}\subseteq \text{SC}\) ⋮ A fast randomized LOGSPACE algorithm for graph connectivity ⋮ A spectrum of time-space trade-offs for undirected \(s-t\) connectivity ⋮ Unnamed Item ⋮ Structure and importance of logspace-MOD class ⋮ Dual VP classes ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Generalized quantifier and a bounded arithmetic theory for LOGCFL ⋮ The complexity of graph connectivity ⋮ Inductive counting below logspace ⋮ Empty alternation ⋮ Adaptive logspace reducibility and parallel time ⋮ Bounded tree-width and LOGCFL ⋮ 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07 ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Properties that characterize LOGCFL ⋮ Characterizing parallel hierarchies by reducibilities ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Lower bounds on the length of universal traversal sequences ⋮ A very hard log-space counting class ⋮ On read-once vs. multiple access to randomness in logspace ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits ⋮ Unnamed Item ⋮ Computing LOGCFL certificates ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Universal traversal sequences for expander graphs ⋮ Tradeoff lower lounds for stack machines ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS ⋮ The complexity of computing maximal word functions

This page was built for publication: Two Applications of Inductive Counting for Complementation Problems