Pages that link to "Item:Q4140967"
From MaRDI portal
The following pages link to Computational Complexity of Probabilistic Turing Machines (Q4140967):
Displayed 50 items.
- 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)
- 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 the complexity of ranking (Q920620) (← links)
- The complexity of power-index comparison (Q1001906) (← 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)
- Probabilistic automata (Q1151262) (← links)
- On tape-bounded probabilistic Turing machine acceptors (Q1158756) (← links)
- Division in idealized unit cost RAMs (Q1159982) (← links)
- Some observations on the probabilistic algorithms and NP-hard problems (Q1163371) (← links)
- Symmetric space-bounded computation (Q1167537) (← links)
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis (Q1168733) (← links)
- On counting problems and the polynomial-time hierarchy (Q1171880) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- An introduction to randomized algorithms (Q1182319) (← links)
- Which new RSA-signatures can be computed from certain given RSA- signatures! (Q1184507) (← links)