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)

• 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
• The complexity properties of probabilistic automata with isolated cut point
• Probabilistic game automata
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Approximation of boolean functions by combinatorial rectangles
• Properties of probabilistic pushdown automata
• On the hardness of analyzing probabilistic programs
• Bayesian estimation and the Kalman filter
• The generation of random numbers that are probably prime
• Turing machines with few accepting computations and low sets for PP
• Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
• Immunity and simplicity in relativizations of probabilistic complexity classes
• Dimension extractors and optimal decompression
• Probabilistic automata
• A note on two-dimensional probabilistic finite automata
• On independent random oracles
• A relation between correctness and randomness in the computation of probabilistic algorithms
• Most relevant explanation: Computational complexity and approximation methods
• On the necessity of Occam algorithms
• Multihead two-way probabilistic finite automata (extended abstract)
• Which new RSA-signatures can be computed from certain given RSA- signatures!
• Restricted relativizations of probabilistic polynomial time
• Synthesizing learners tolerating computable noisy data
• Structural complexity theory: Recent surprises
• On the complexity of ranking
• Generality's price: Inescapable deficiencies in machine-learned programs
• Probabilistic Turing machines and recursively enumerable Dedekind cuts
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Phase transitions of PP-complete satisfiability problems
• Graph isomorphism is low for PP
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Open-world probabilistic databases: semantics, algorithms, complexity
• On small generators
• An upward measure separation theorem
• A note on enumerative counting
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterizations of semantic domains for randomized algorithms
• Randomised algorithms
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• Pseudorandom sources for BPP
• 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

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)