Some observations on the probabilistic algorithms and NP-hard problems
From MaRDI portal
Publication:1163371
DOI10.1016/0020-0190(82)90139-9zbMath0483.68045MaRDI QIDQ1163371
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90139-9
Related Items
Monotonous and randomized reductions to sparse sets, Generalized lowness and highness and probabilistic complexity classes, On closure properties of bounded two-sided error complexity classes, On quasilinear-time complexity theory, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, BPP and the polynomial hierarchy, Does co-NP have short interactive proofs ?, Probabilistic quantifiers and games, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Probabilistic complexity classes and lowness, Computational complexity of loss networks, Approximation of boolean functions by combinatorial rectangles, Polynomial time samplable distributions, Degrees of Dowd-type generic oracles, Bounded truth table does not reduce the one-query tautologies to a random oracle, Error-bounded probabilistic computations between MA and AM, Resource bounded symmetry of information revisited, A Downward Collapse within the Polynomial Hierarchy
Cites Work
- Unnamed Item
- Riemann's hypothesis and tests for primality
- The polynomial-time hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Every Prime Has a Succinct Certificate
- A Fast Monte-Carlo Test for Primality
- Computational Complexity of Probabilistic Turing Machines
- Relativized questions involving probabilistic algorithms
