The relative complexity of NP search problems
type: Item
instance of: scholarly article
title: The relative complexity of NP search problems
zbMATH Open document ID: 0920.68051
author: Jeff Edmonds
author: Russell Impagliazzo
author: Toniann Pitassi
author: Paul Beame
author: Stephen Cook
published in: Journal of Computer and System Sciences
publication date: 1999-09-13T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1236446
zbMATH Keywords: NP search problems
MaRDI profile type: Publication
full work available at URL: jcss.1998.1575
OpenAlex ID: W2037028865
cites work: A tight relationship between generic oracles and type-2 complexity theory
cites work: Self-witnessing polynomial-time complexity and prime factorization
cites work: One-way functions and the nonisomorphism of NP-complete sets
cites work: How easy is local search?
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Every Prime Has a Succinct Certificate
cites work: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
cites work: Complexity for type-2 relations
DOI: 10.1006/JCSS.1998.1575
description: scientific article; zbMATH DE number 1236446