Computational Complexity of Probabilistic Turing Machines

DOI10.1137/0206049zbMATH Open0366.02024OpenAlexW2059442002WikidataQ60305282 ScholiaQ60305282MaRDI QIDQ4140967FDOQ4140967

Authors: John Gill 

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206049

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Cited In (only showing first 100 items - show all)

• Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
• Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems
• Deterministic and randomized polynomial‐time approximation of radii
• Symmetric space-bounded computation
• Quantum computing, postselection, and probabilistic polynomial-time
• The complexity of the \(K\)th largest subset problem and related problems
• Probabilistic quantifiers and games
• On tape-bounded probabilistic Turing machine acceptors
• Some observations on the probabilistic algorithms and NP-hard problems
• Strong and robustly strong polynomial-time reducibilities to sparse sets
• Separating complexity classes with tally oracles
• Computational depth and reducibility
• The random oracle hypothesis is false
• A probabilistic model of computing with words
• Enumerative counting is hard
• Oracle Quantum Computing
• On the complexity of graph reconstruction
• On balanced versus unbalanced computation trees
• On read-once vs. multiple access to randomness in logspace
• Space-bounded hierarchies and probabilistic computations
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Random generation of combinatorial structures from a uniform distribution
• Probabilistic polynomial time is closed under parity reductions
• Lower space bounds for randomized computation
• Randomized algorithms in combinatorial optimization: A survey
• On the power of Las Vegas II: Two-way finite automata
• Collapse of PP with a semi-random source to BPP
• Complexity limitations on quantum computation
• Most probable explanations in Bayesian networks: complexity and tractability
• The complexity of power-index comparison
• Classes of bounded nondeterminism
• Minimum disclosure proofs of knowledge
• Relativized alternation and space-bounded computation
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Logarithmic advice classes
• Title not available (Why is that?)
• On sparse hard sets for counting classes
• Testable and untestable classes of first-order formulae
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Kolmogorov characterizations of complexity classes
• Amplification of slight probabilistic advantage at absolutely no cost in space
• New collapse consequences of NP having small circuits
• Relativized counting classes: Relations among thresholds, parity, and mods
• Games against nature
• Counting classes: Thresholds, parity, mods, and fewness
• Robust algorithms: a different approach to oracles
• Probabilistic communication complexity
• On helping by robust oracle machines
• Complexity classes without machines: on complete languages for UP
• On the relative complexity of hard problems for complexity classes without complete problems
• Relativized circuit complexity
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The complexity of combinatorial problems with succinct input representation
• Factoring polynomials over finite fields: A survey
• The consequences of eliminating NP solutions
• BPP and the polynomial hierarchy
• Simple characterizations of \(P(\# P)\) and complete problems
• Computation times of NP sets of different densities
• Space-bounded quantum complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• On counting problems and the polynomial-time hierarchy
• Structural control in weighted voting games
• Approximate counting in bounded arithmetic
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Error-bounded probabilistic computations between MA and AM
• Relationships among $PL$, $\#L$, and the determinant
• On the autoreducibility of functions
• On the power of generalized Mod-classes
• Fault-tolerance and complexity (extended abstract)
• Lower bounds on the length of universal traversal sequences
• Gap-definable counting classes
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Complexity results for structure-based causality.
• Classifying the computational complexity of problems
• Division in idealized unit cost RAMs
• Multihead two-way probabilistic finite automata
• Graph isomorphism is in the low hierarchy
• An introduction to randomized algorithms
• Probabilistic complexity classes and lowness
• Theory of one-tape linear-time Turing machines
• The many forms of hypercomputation
• The complexity of stochastic games
• A complexity theory for feasible closure properties
• The complexity of the max word problem and the power of one-way interactive proof systems
• A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Decreasing the bandwidth of a transition matrix
• Prediction-preserving reducibility
• On probabilistic space-bounded machines with multiple access to random tape
• Approximation to measurable functions and its relation to probabilistic computation
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Randomization for robot tasks: using dynamic programming in the space of knowledge states
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Some observations on the connection between counting and recursion
• The time-precision tradeoff problem on on-line probabilistic Turing machines
• Promise problems and access to unambiguous computation

This page was built for publication: Computational Complexity of Probabilistic Turing Machines

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