Two Applications of Inductive Counting for Complementation Problems

DOI10.1137/0218038MaRDI QIDQ3835019zbMATH OpenOpenAlexWikidataFDO

Authors Allan Borodin, Walter L. Ruzzo, Martin Tompa, Stephen Cook, P. 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

random walkhierarchyconnectivitypebblingNCcomplementationprobabilistic algorithmLOGCFLsemi-unboundednessinductive countingsymmetric computation

Mathematics Subject Classification ID

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

Recommendations

• Inductive counting below LOGSPACE
• scientific article; zbMATH DE number 1101597
• Inductive counting for width-restricted branching programs
• Using inductive counting to simulate nondeterministic computation
• A variant of inductive counting

Cited in

(37)

• scientific article; zbMATH DE number 18628 (Why is no real title available?)
• 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• The electrical resistance of a graph captures its commute and cover times
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• A very hard log-space counting class
• Structure and importance of logspace-MOD class
• Computing LOGCFL certificates
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Universal traversal sequences for expander graphs
• On adaptive DLOGTIME and POLYLOGTIME reductions
• On read-once vs. multiple access to randomness in logspace
• Equivalence classes and conditional hardness in massively parallel computations
• Context-free grammars with linked nonterminals
• \(\text{RL}\subseteq \text{SC}\)
• The complexity of graph connectivity
• The parameterized space complexity of model-checking bounded variable first-order logic
• A spectrum of time-space trade-offs for undirected s-t connectivity
• Characterizing parallel hierarchies by reducibilities
• The complexity of computing maximal word functions
• Inductive counting below LOGSPACE
• Generalized quantifier and a bounded arithmetic theory for LOGCFL
• Tradeoff lower lounds for stack machines
• Properties that characterize LOGCFL
• Bounded tree-width and LOGCFL
• Relationships among $PL$, $\#L$, and the determinant
• Lower bounds on the length of universal traversal sequences
• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
• Adaptive logspace reducibility and parallel time
• Depth lower bounds for monotone semi-unbounded fan-in circuits.
• A fast randomized LOGSPACE algorithm for graph connectivity
• Empty alternation
• Dual VP classes
• A variant of inductive counting
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3835019)