Computational Complexity of Probabilistic Turing Machines
From MaRDI portal
Publication:4140967
DOI10.1137/0206049zbMath0366.02024OpenAlexW2059442002WikidataQ60305282 ScholiaQ60305282MaRDI QIDQ4140967
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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)
Related Items
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, Flow in networks with random capacities, The Bayesian ontology language \(\mathcal {BEL}\), A complexity theory for feasible closure properties, Generality's price: Inescapable deficiencies in machine-learned programs, Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Confluent complement: an algorithm for the intersection of face ideals, Immunity and Simplicity for Exact Counting and Other Counting Classes, The Odds of Staying on Budget, What is the Church-Turing Thesis?, Structural complexity theory: Recent surprises, Probabilistic causes in Markov chains, Approximate Degree in Classical and Quantum Computing, Infinite vs. finite size-bounded randomized computations, Relativized counting classes: Relations among thresholds, parity, and mods, Pseudorandom sources for BPP, Simultaneous strong separations of probabilistic and unambiguous complexity classes, Bayesian estimation and the Kalman filter, Phase transitions of PP-complete satisfiability problems, Unnamed Item, Generalized theorems on relationships among reducibility notions to certain complexity classes, On the complexity of graph reconstruction, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Characterizing polynomial complexity classes by reducibilities, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, Machines that perform measurements, Promise problems and access to unambiguous computation, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, Unnamed Item, Interference as a computational resource: a tutorial, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, On the power of generalized Mod-classes, Classifying the computational complexity of problems, SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Immunity and simplicity in relativizations of probabilistic complexity classes, Isolation, matching, and counting uniform and nonuniform upper bounds, Complexity limitations on quantum computation, Space-bounded quantum complexity, A structured view on weighted counting with relations to counting, quantum computation and applications, On Higher-Order Probabilistic Subrecursion, On balanced versus unbalanced computation trees, Relationships among $PL$, $\#L$, and the determinant, Fault-tolerance and complexity (Extended abstract), Lower space bounds for randomized computation, Strong self-reducibility precludes strong immunity, Immunity, simplicity, probabilistic complexity classes and relativizations, The hardest halfspace, Open-world probabilistic databases: semantics, algorithms, complexity, A monad for randomized algorithms, New collapse consequences of NP having small circuits, Factoring polynomials over finite fields: A survey, On the power of randomized multicounter machines, Counting classes: Thresholds, parity, mods, and fewness, Approximate counting in bounded arithmetic, Quantum and classical complexity classes: Separations, collapses, and closure properties, Classes of bounded nondeterminism, Quantum computing, postselection, and probabilistic polynomial-time, Synthesizing learners tolerating computable noisy data, A relation between correctness and randomness in the computation of probabilistic algorithms, A probabilistic model of computing with words, The many forms of hypercomputation, Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes, Unnamed Item, Properties of probabilistic pushdown automata, Unnamed Item, Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems, Error-bounded probabilistic computations between MA and AM, On the power of Las Vegas II: Two-way finite automata, Deterministic and randomized polynomial‐time approximation of radii, Multihead two-way probabilistic finite automata, Complexity results for probabilistic answer set programming, A thesis for interaction, Monotonous and randomized reductions to sparse sets, 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, Graph isomorphism is low for PP, Enumerative counting is hard, Probabilistic game automata, Generalized lowness and highness and probabilistic complexity classes, Characterizations of semantic domains for randomized algorithms, Inconsistency-Tolerant Query Answering: Rationality Properties and Computational Complexity Analysis, Randomised algorithms, The time-precision tradeoff problem on on-line probabilistic Turing machines, CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES, Oracle Quantum Computing, A note on the circuit complexity of PP, Complexity results for structure-based causality., Structural control in weighted voting games, Tally NP sets and easy census functions., A higher-order characterization of probabilistic polynomial time, Unnamed Item, On measure quantifiers in first-order arithmetic
