Computational Complexity of Probabilistic Turing Machines
From MaRDI portal
Publication:4140967
Cited in
(only showing first 100 items - show all)- A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
- Prediction-preserving reducibility
- On probabilistic space-bounded machines with multiple access to random tape
- The hardest halfspace
- Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems
- Approximation to measurable functions and its relation to probabilistic computation
- What is the Church-Turing Thesis?
- Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Randomization for robot tasks: using dynamic programming in the space of knowledge states
- A note on the circuit complexity of PP
- Symmetric space-bounded computation
- Deterministic and randomized polynomial‐time approximation of radii
- The complexity of the Kth largest subset problem and related problems
- Immunity, simplicity, probabilistic complexity classes and relativizations
- Probabilistic quantifiers and games
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Separating complexity classes with tally oracles
- On tape-bounded probabilistic Turing machine acceptors
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Some observations on the probabilistic algorithms and NP-hard problems
- Some observations on the connection between counting and recursion
- Quantum computing, postselection, and probabilistic polynomial-time
- Computational depth and reducibility
- The time-precision tradeoff problem on on-line probabilistic Turing machines
- On higher-order probabilistic subrecursion
- The random oracle hypothesis is false
- A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
- A probabilistic model of computing with words
- A randomised heuristical algorithm for estimating the chromatic number of a graph
- Properties of probabilistic pushdown automata
- Promise problems and access to unambiguous computation
- Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
- The complexity properties of probabilistic automata with isolated cut point
- Probabilistic causes in Markov chains
- Probabilistic game automata
- Enumerative counting is hard
- On measure quantifiers in first-order arithmetic
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
- Oracle Quantum Computing
- Tally NP sets and easy census functions.
- Characterizing polynomial complexity classes by reducibilities
- On the complexity of graph reconstruction
- Approximation of boolean functions by combinatorial rectangles
- On balanced versus unbalanced computation trees
- A monad for randomized algorithms
- On read-once vs. multiple access to randomness in logspace
- Properties of probabilistic pushdown automata
- 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
- Randomized algorithms in combinatorial optimization: A survey
- On the hardness of analyzing probabilistic programs
- Collapse of PP with a semi-random source to BPP
- Bayesian estimation and the Kalman filter
- The computational complexity of calculating partition functions of optimal medians with Hamming distance
- Descriptive complexity for counting complexity classes
- The generation of random numbers that are probably prime
- Lower space bounds for randomized computation
- Recursion theoretic characterizations of complexity classes of counting functions
- On the power of Las Vegas II: Two-way finite automata
- Most probable explanations in Bayesian networks: complexity and tractability
- Turing machines with few accepting computations and low sets for PP
- Complexity limitations on quantum computation
- The complexity of power-index comparison
- Minimum disclosure proofs of knowledge
- Classes of bounded nondeterminism
- Relativized alternation and space-bounded computation
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Logarithmic advice classes
- Confluent complement: an algorithm for the intersection of face ideals
- On sparse hard sets for counting classes
- Testable and untestable classes of first-order formulae
- Immunity and simplicity in relativizations of probabilistic complexity classes
- scientific article; zbMATH DE number 6866233 (Why is no real title available?)
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
- Approximate counting, uniform generation and rapidly mixing Markov chains
- The odds of staying on budget
- Kolmogorov characterizations of complexity classes
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- On the power of randomized multicounter machines
- Infinite vs. finite size-bounded randomized computations
- Amplification of slight probabilistic advantage at absolutely no cost in space
- Flow in networks with random capacities
- Inconsistency-tolerant query answering: rationality properties and computational complexity analysis
- Games against nature
- Dimension extractors and optimal decompression
- Probabilistic communication complexity
- Relativized counting classes: Relations among thresholds, parity, and mods
- New collapse consequences of NP having small circuits
- Robust algorithms: a different approach to oracles
- Probabilistic automata
- 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
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)
