Computational Complexity of Probabilistic Turing Machines

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

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
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
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
Multihead two-way probabilistic finite automata
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
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
Fault-tolerance and complexity (Extended abstract)
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

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)