Pages that link to "Item:Q4140967"
From MaRDI portal
The following pages link to Computational Complexity of Probabilistic Turing Machines (Q4140967):
Displaying 50 items.
- Collapse of PP with a semi-random source to BPP (Q286973) (← links)
- Most probable explanations in Bayesian networks: complexity and tractability (Q433524) (← links)
- Testable and untestable classes of first-order formulae (Q440006) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- Probabilistic communication complexity (Q579927) (← links)
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata (Q596324) (← links)
- Decreasing the bandwidth of a transition matrix (Q673904) (← links)
- Multihead two-way probabilistic finite automata (Q675857) (← links)
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
- Randomization for robot tasks: using dynamic programming in the space of knowledge states (Q686748) (← links)
- Probabilistic polynomial time is closed under parity reductions (Q751270) (← links)
- Prediction-preserving reducibility (Q756441) (← links)
- Most relevant explanation: Computational complexity and approximation methods (Q766267) (← links)
- On small generators (Q802309) (← links)
- Probabilistic Turing machines and recursively enumerable Dedekind cuts (Q802546) (← links)
- Kolmogorov characterizations of complexity classes (Q804291) (← links)
- An upward measure separation theorem (Q808696) (← links)
- A note on enumerative counting (Q809598) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P (Q845727) (← links)
- The complexity of the \(K\)th largest subset problem and related problems (Q894449) (← links)
- On the complexity of ranking (Q920620) (← links)
- On the autoreducibility of functions (Q970103) (← links)
- The complexity of power-index comparison (Q1001906) (← links)
- Dimension extractors and optimal decompression (Q1015378) (← links)
- Theory of one-tape linear-time Turing machines (Q1041220) (← links)
- BPP and the polynomial hierarchy (Q1052094) (← links)
- Space-bounded hierarchies and probabilistic computations (Q1062759) (← links)
- Robust algorithms: a different approach to oracles (Q1063417) (← links)
- Games against nature (Q1069296) (← links)
- Relativized circuit complexity (Q1069299) (← links)
- Randomized algorithms in combinatorial optimization: A survey (Q1077329) (← links)
- Random generation of combinatorial structures from a uniform distribution (Q1079379) (← links)
- Approximation to measurable functions and its relation to probabilistic computation (Q1088659) (← links)
- The complexity of combinatorial problems with succinct input representation (Q1090455) (← links)
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes (Q1094874) (← links)
- On helping by robust oracle machines (Q1097695) (← links)
- Some observations on the connection between counting and recursion (Q1098837) (← links)
- The complexity properties of probabilistic automata with isolated cut point (Q1102752) (← links)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes (Q1106840) (← links)
- Does co-NP have short interactive proofs ? (Q1108004) (← links)
- Complexity classes without machines: on complete languages for UP (Q1109566) (← links)
- Minimum disclosure proofs of knowledge (Q1110348) (← links)
- Relativized alternation and space-bounded computation (Q1111024) (← links)
- On the relative complexity of hard problems for complexity classes without complete problems (Q1112017) (← links)
- Probabilistic quantifiers and games (Q1112019) (← links)
- Graph isomorphism is in the low hierarchy (Q1116696) (← links)
- Approximate counting, uniform generation and rapidly mixing Markov chains (Q1117955) (← links)
- The generation of random numbers that are probably prime (Q1118632) (← links)
- Deterministic simulation of tape-bounded probabilistic Turing machine transducers (Q1143792) (← links)
