Computational Complexity of Probabilistic Turing Machines

DOI10.1137/0206049zbMath0366.02024OpenAlexW2059442002WikidataQ60305282 ScholiaQ60305282MaRDI QIDQ4140967

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

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

Related Items (only showing first 100 items - show all)

Randomized algorithms in combinatorial optimization: A survey ⋮ Random generation of combinatorial structures from a uniform distribution ⋮ Simple characterizations of \(P(\# P)\) and complete problems ⋮ The random oracle hypothesis is false ⋮ Computational depth and reducibility ⋮ Collapse of PP with a semi-random source to BPP ⋮ On closure properties of GapP ⋮ Approximation to measurable functions and its relation to probabilistic computation ⋮ The complexity of combinatorial problems with succinct input representation ⋮ The computational complexity of calculating partition functions of optimal medians with Hamming distance ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ Computation times of NP sets of different densities ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ On helping by robust oracle machines ⋮ Lower bounds for one-way probabilistic communication complexity and their application to space complexity ⋮ Some observations on the connection between counting and recursion ⋮ Efficient simulations by a biased coin ⋮ The statistics of state-spaces ⋮ The complexity properties of probabilistic automata with isolated cut point ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Does co-NP have short interactive proofs ? ⋮ Complexity classes without machines: on complete languages for UP ⋮ Minimum disclosure proofs of knowledge ⋮ Relativized alternation and space-bounded computation ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ Probabilistic quantifiers and games ⋮ Graph isomorphism is in the low hierarchy ⋮ Approximate counting, uniform generation and rapidly mixing Markov chains ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ The generation of random numbers that are probably prime ⋮ The complexity of the \(K\)th largest subset problem and related problems ⋮ Deterministic simulation of tape-bounded probabilistic Turing machine transducers ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Probabilistic automata ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ Testable and untestable classes of first-order formulae ⋮ On tape-bounded probabilistic Turing machine acceptors ⋮ Division in idealized unit cost RAMs ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Some observations on the probabilistic algorithms and NP-hard problems ⋮ On the complexity of ranking ⋮ The consequences of eliminating NP solutions ⋮ Symmetric space-bounded computation ⋮ Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis ⋮ On counting problems and the polynomial-time hierarchy ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ On the hardness of analyzing probabilistic programs ⋮ An introduction to randomized algorithms ⋮ Which new RSA-signatures can be computed from certain given RSA- signatures! ⋮ On independent random oracles ⋮ Separating complexity classes with tally oracles ⋮ Restricted relativizations of probabilistic polynomial time ⋮ The complexity of stochastic games ⋮ Decreasing the bandwidth of a transition matrix ⋮ Multihead two-way probabilistic finite automata ⋮ Turing machines with few accepting computations and low sets for PP ⋮ A survey of space complexity ⋮ On the necessity of Occam algorithms ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Logarithmic advice classes ⋮ A note on the permanent value problem ⋮ An almost-constant round interactive zero-knowledge proof ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Randomization for robot tasks: using dynamic programming in the space of knowledge states ⋮ Lower bounds on the length of universal traversal sequences ⋮ On read-once vs. multiple access to randomness in logspace ⋮ On sparse hard sets for counting classes ⋮ Graph isomorphism is low for PP ⋮ On the autoreducibility of functions ⋮ Probabilistic communication complexity ⋮ The complexity of power-index comparison ⋮ A randomised heuristical algorithm for estimating the chromatic number of a graph ⋮ Dimension extractors and optimal decompression ⋮ Probabilistic complexity classes and lowness ⋮ Probabilistic polynomial time is closed under parity reductions ⋮ Prediction-preserving reducibility ⋮ Properties of probabilistic pushdown automata ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Circuits over PP and PL ⋮ Most relevant explanation: Computational complexity and approximation methods ⋮ \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\) ⋮ Theory of one-tape linear-time Turing machines ⋮ A note on two-dimensional probabilistic finite automata ⋮ BPP and the polynomial hierarchy ⋮ Voronoi-like nondeterministic partition of a lattice by collectives of finite automata ⋮ On small generators ⋮ Space-bounded hierarchies and probabilistic computations ⋮ Probabilistic Turing machines and recursively enumerable Dedekind cuts ⋮ The complexity of the max word problem and the power of one-way interactive proof systems ⋮ Robust algorithms: a different approach to oracles ⋮ Kolmogorov characterizations of complexity classes ⋮ An upward measure separation theorem ⋮ A note on enumerative counting ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ Gap-definable counting classes ⋮ Games against nature ⋮ Relativized circuit complexity ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space

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