Parallel computation for well-endowed rings and space-bounded probabilistic machines
From MaRDI portal
Publication:3732965
DOI10.1016/S0019-9958(83)80060-6zbMath0598.68043OpenAlexW2056352038MaRDI QIDQ3732965
Allan Borodin, Stephen A. Cook, Nicholas J. Pippenger
Publication date: 1983
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(83)80060-6
parallel machinesimulationscompletion of stochastic matricesdeterministic machineprobabilistic Turing acceptor
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Stochastic matrices (15B51) Turing machines and related notions (03D10) Associative rings and algebras with additional structure (16W99)
Related Items
Oracle computations in parallel numerical linear algebra, Fast parallel absolute irreducibility testing, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, 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, On path equivalence of nondeterministic finite automata, Inversion in finite fields using logarithmic depth, On the parallel complexity of linear groups, Constructing a perfect matching is in random NC, On randomized versus deterministic computation, 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, On some variations of two-way probabilistic finite automata models, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, Isolation, matching, and counting uniform and nonuniform upper bounds, Space-bounded quantum complexity, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, A Complete Characterization of Unitary Quantum Space, Relationships among $PL$, $\#L$, and the determinant, Circuits for computing the GCD of two polynomials over an algebraic number field, Lower space bounds for randomized computation, Matrix inversion in RNC\(^ 1\), Decreasing the bandwidth of a transition matrix, Multihead two-way probabilistic finite automata, Closed timelike curves make quantum and classical computing equivalent, Advice Coins for Classical and Quantum Computation, A survey of space complexity, The computational complexity of universal hashing, On read-once vs. multiple access to randomness in logspace, Linear matroid intersection is in quasi-NC, Exponential separation of quantum and classical online space complexity, Multihead two-way probabilistic finite automata, Improved processor bounds for combinatorial problems in RNC, An application of quantum finite automata to interactive proof systems, Circuits over PP and PL, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Bipartite Perfect Matching is in Quasi-NC, Space-bounded hierarchies and probabilistic computations
