Parallel computation for well-endowed rings and space-bounded probabilistic machines
From MaRDI portal
Publication:3732965
DOI10.1016/S0019-9958(83)80060-6zbMath0598.68043MaRDI QIDQ3732965
Allan Borodin, Nicholas J. Pippenger, Stephen A. Cook
Publication date: 1983
Published in: Information and Control (Search for Journal in Brave)
parallel machine; simulations; completion of stochastic matrices; deterministic machine; probabilistic Turing acceptor
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
15B51: Stochastic matrices
03D10: Turing machines and related notions
16W99: Associative rings and algebras with additional structure
Related Items
Relationships among $PL$, $\#L$, and the determinant, Decreasing the bandwidth of a transition matrix, Multihead two-way probabilistic finite automata, Exponential separation of quantum and classical online space complexity, On some variations of two-way probabilistic finite automata models, An application of quantum finite automata to interactive proof systems, Space-bounded hierarchies and probabilistic computations, Fast parallel absolute irreducibility testing, Polynomial division and its computational complexity, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, Matching is as easy as matrix inversion, Sequential and parallel complexity of approximate evaluation of polynomial zeros, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Constructing a perfect matching is in random NC, Relativized alternation and space-bounded computation, The iterated mod problem, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Circuits for computing the GCD of two polynomials over an algebraic number field, Matrix inversion in RNC\(^ 1\), A survey of space complexity, The computational complexity of universal hashing, On read-once vs. multiple access to randomness in logspace, Improved processor bounds for combinatorial problems in RNC, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Oracle computations in parallel numerical linear algebra, On path equivalence of nondeterministic finite automata, On randomized versus deterministic computation, Circuits over PP and PL, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Isolation, matching, and counting uniform and nonuniform upper bounds, Space-bounded quantum complexity, Inversion in finite fields using logarithmic depth, On the parallel complexity of linear groups
