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

complementationconnectivityhierarchyinductive countingLOGCFLNCpebblingprobabilistic algorithmrandom walksemi-unboundednesssymmetric computation

Mathematics Subject Classification ID

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

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

(42)

• Properties that characterize LOGCFL
• Characterizing parallel hierarchies by reducibilities
• 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
• The complexity of computing maximal word functions
• \(\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
• The electrical resistance of a graph captures its commute and cover times
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• A variant of inductive counting
• Universal traversal sequences for expander graphs
• Equivalence classes and conditional hardness in massively parallel computations
• Dual VP classes
• Depth lower bounds for monotone semi-unbounded fan-in circuits.
• Context-free grammars with linked nonterminals
• scientific article; zbMATH DE number 18628 (Why is no real title available?)
• Structure and importance of logspace-MOD class
• Adaptive logspace reducibility and parallel time
• scientific article; zbMATH DE number 1101597 (Why is no real title available?)
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• Relationships among $PL$, $\#L$, and the determinant
• The parameterized space complexity of model-checking bounded variable first-order logic
• The complexity of graph connectivity
• Inductive counting below LOGSPACE
• Empty alternation
• 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Computing LOGCFL certificates
• Bounded tree-width and LOGCFL
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
• On adaptive DLOGTIME and POLYLOGTIME reductions
• Inductive counting for width-restricted branching programs
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• Alternation-bounded semi-unbounded fan-in cascading circuits and the complementation closure property
• Catalytic computing and register programs beyond log-depth
• Languages of words of low automatic complexity are hard to compute
• Tradeoff lower lounds for stack machines
• Generalized quantifier and a bounded arithmetic theory for LOGCFL
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

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)