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
• What is the Church-Turing Thesis?
• The hardest halfspace
• A note on the circuit complexity of PP
• Immunity, simplicity, probabilistic complexity classes and relativizations
• A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
• On higher-order probabilistic subrecursion
• Properties of probabilistic pushdown automata
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• A randomised heuristical algorithm for estimating the chromatic number of a graph
• Probabilistic causes in Markov chains
• On measure quantifiers in first-order arithmetic
• Characterizing polynomial complexity classes by reducibilities
• Tally NP sets and easy census functions.
• A monad for randomized algorithms
• Descriptive complexity for counting complexity classes
• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• Recursion theoretic characterizations of complexity classes of counting functions
• Confluent complement: an algorithm for the intersection of face ideals
• The odds of staying on budget
• On the power of randomized multicounter machines
• Infinite vs. finite size-bounded randomized computations
• Flow in networks with random capacities
• Inconsistency-tolerant query answering: rationality properties and computational complexity analysis
• A higher-order characterization of probabilistic polynomial time
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
• A thesis for interaction
• On the power of counting the total number of computation paths of NPTMs
• On closure properties of GapP
• Machines that perform measurements
• Semiring reasoning frameworks in AI and their computational complexity
• Interference as a computational resource: a tutorial
• Approximating iterated multiplication of stochastic matrices in small space
• A survey of space complexity
• Efficient simulations by a biased coin
• Strong self-reducibility precludes strong immunity
• A note on the permanent value problem
• An almost-constant round interactive zero-knowledge proof
• Approximate Degree in Classical and Quantum Computing
• Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
• A note on two-dimensional probabilistic Turing machines
• A probabilistic approach to navigation in Hypertext
• The statistics of state-spaces
• Graph isomorphism is low for PP
• A space lower bound for \(st\)-connectivity on node-named JAGs
• Circuits over PP and PL
• Title not available (Why is that?)
• Monotonous and randomized reductions to sparse sets
• Generalized lowness and highness and probabilistic complexity classes
• The Bayesian ontology language \(\mathcal {BEL}\)

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)