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 hierarchypolynomial time computation

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Every Prime Has a Succinct Certificate
• 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)

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