Some observations on the probabilistic algorithms and NP-hard problems
type: Item
instance of: scholarly article
title: Some observations on the probabilistic algorithms and NP-hard problems
zbMATH Open document ID: 0483.68045
DOI: 10.1016/0020-0190(82)90139-9
published in: Information Processing Letters
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3759549
zbMATH Keywords: polynomial time computation
zbMATH Keywords: nondeterminism
zbMATH Keywords: polynomial time hierarchy
author: Ker-I Ko
MaRDI profile type: Publication
full work available at URL: 0020-0190(82)90139-9
OpenAlex ID: W2011358434
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Riemann's hypothesis and tests for primality
cites work: Every Prime Has a Succinct Certificate
cites work: Q4164569
cites work: Relativized questions involving probabilistic algorithms
cites work: A Fast Monte-Carlo Test for Primality
cites work: The polynomial-time hierarchy
description: scientific article; zbMATH DE number 3759549