Some observations on the probabilistic algorithms and NP-hard problems

DOI10.1016/0020-0190(82)90139-9zbMath0483.68045OpenAlexW2011358434MaRDI QIDQ1163371

Ker-I. Ko

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

zbMATH Keywords

nondeterminismpolynomial time hierarchypolynomial time computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items (27)

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Does co-NP have short interactive proofs ? ⋮ Probabilistic quantifiers and games ⋮ On closure properties of bounded two-sided error complexity classes ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ On quasilinear-time complexity theory ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Equivalence problems for circuits over sets of natural numbers ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Natural Proofs versus Derandomization ⋮ Approximating the partition function of planar two-state spin systems ⋮ Probabilistic complexity classes and lowness ⋮ Monotonous and randomized reductions to sparse sets ⋮ Generalized lowness and highness and probabilistic complexity classes ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Polynomial time samplable distributions ⋮ BPP and the polynomial hierarchy ⋮ Resource bounded symmetry of information revisited ⋮ Degrees of Dowd-type generic oracles ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ Computational complexity of loss networks

Cites Work

• 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
• Unnamed Item

This page was built for publication: Some observations on the probabilistic algorithms and NP-hard problems