Some observations on the probabilistic algorithms and NP-hard problems

DOI10.1016/0020-0190(82)90139-9MaRDI QIDQ1163371zbMATH OpenOpenAlexFDO

Authors 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 computationpolynomial time hierarchy

Mathematics Subject Classification ID

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

Cites work

• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Every Prime Has a Succinct Certificate
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativized questions involving probabilistic algorithms
• Riemann's hypothesis and tests for primality
• The polynomial-time hierarchy

Cited in

(26)

• 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
• Equivalence problems for circuits over sets of natural numbers
• 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
• In Memoriam: Ker-I Ko (1950–2018)
• A Downward Collapse within the Polynomial Hierarchy
• Fault-tolerance and complexity (extended abstract)
• 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
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks
• On quasilinear-time complexity theory
• Approximating the partition function of planar two-state spin systems
• 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?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1163371)