Pages that link to "Item:Q4140967"
From MaRDI portal
The following pages link to Computational Complexity of Probabilistic Turing Machines (Q4140967):
Displaying 50 items.
- 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)
- On independent random oracles (Q1185000) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Restricted relativizations of probabilistic polynomial time (Q1186606) (← links)
- The complexity of stochastic games (Q1187025) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- A survey of space complexity (Q1193412) (← links)
- On the necessity of Occam algorithms (Q1193631) (← links)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P (Q1193633) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- A note on the permanent value problem (Q1198001) (← links)
- An almost-constant round interactive zero-knowledge proof (Q1198029) (← links)
- Lower bounds on the length of universal traversal sequences (Q1201151) (← links)
- On read-once vs. multiple access to randomness in logspace (Q1208412) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- A randomised heuristical algorithm for estimating the chromatic number of a graph (Q1262784) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- Properties of probabilistic pushdown automata (Q1274989) (← links)
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\) (Q1288206) (← links)
- A note on two-dimensional probabilistic finite automata (Q1298347) (← links)
- The complexity of the max word problem and the power of one-way interactive proof systems (Q1312183) (← links)
- Gap-definable counting classes (Q1318473) (← links)
- Simple characterizations of \(P(\# P)\) and complete problems (Q1333395) (← links)
- The random oracle hypothesis is false (Q1333397) (← links)
- Computational depth and reducibility (Q1334655) (← links)
- On closure properties of GapP (Q1337146) (← links)
- Computation times of NP sets of different densities (Q1348523) (← links)
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity (Q1351496) (← links)
- Efficient simulations by a biased coin (Q1352086) (← links)
- The statistics of state-spaces (Q1356182) (← links)
- Recursion theoretic characterizations of complexity classes of counting functions (Q1365942) (← links)
- Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
- A space lower bound for \(st\)-connectivity on node-named JAGs (Q1566733) (← links)
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits (Q1567407) (← links)
- Circuits over PP and PL (Q1567408) (← links)
- Voronoi-like nondeterministic partition of a lattice by collectives of finite automata (Q1596777) (← links)
- Amplification of slight probabilistic advantage at absolutely no cost in space (Q1607005) (← links)
- The computational complexity of calculating partition functions of optimal medians with Hamming distance (Q1631451) (← links)
- The complexity of Bayesian networks specified by propositional and relational languages (Q1711881) (← links)
- On the hardness of analyzing probabilistic programs (Q1733103) (← links)
