Some observations on the probabilistic algorithms and NP-hard problems
From MaRDI portal
Publication:1163371
DOI10.1016/0020-0190(82)90139-9zbMATH Open0483.68045OpenAlexW2011358434MaRDI QIDQ1163371FDOQ1163371
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
Cites Work
- Riemann's hypothesis and tests for primality
- A Fast Monte-Carlo Test for Primality
- The polynomial-time hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Title not available (Why is that?)
- 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
Cited In (26)
- Probabilistic quantifiers and games
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Degrees of Dowd-type generic oracles
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- Approximation of boolean functions by combinatorial rectangles
- 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
- Generalized lowness and highness and probabilistic complexity classes
- Nonuniform proof systems: A new framework to describe nonuniform 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)
