Two Applications of Inductive Counting for Complementation Problems

DOI10.1137/0218038zbMath0678.68031WikidataQ29542907 ScholiaQ29542907MaRDI QIDQ3835019

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

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

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60G50: Sums of independent random variables; random walks

91A05: 2-person games

68Q45: Formal languages and automata

68R10: Graph theory (including graph drawing) in computer science

94C99: Circuits, networks

03D55: Hierarchies of computability and definability

Related Items

Adaptive logspace reducibility and parallel time, Relationships among $PL$, $\#L$, and the determinant, Computing LOGCFL certificates, On adaptive DLOGTIME and POLYLOGTIME reductions, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, 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, Universal traversal sequences for expander graphs, Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits, Structure and importance of logspace-MOD class