Promise problems complete for complexity classes
type: Item
instance of: scholarly article
title: Promise problems complete for complexity classes
zbMATH Open document ID: 0655.68050
DOI: 10.1016/0890-5401(88)90030-2
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4070316
zbMATH Keywords: hardness results
zbMATH Keywords: promise problems
zbMATH Keywords: self-reducible decision problems
zbMATH Keywords: graph isomorphism
author: Alan L. Selman
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90030-2
OpenAlex ID: W2066390433
cites work: Comparing complexity classes
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Cryptocomplexity and NP-completeness
cites work: Q4198056
cites work: Q3328286
cites work: Q3862379
cites work: Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes
cites work: On self-reducibility and weak P-selectivity
cites work: A comparison of polynomial time reducibilities
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
cites work: Reductions on NP and p-selective sets
cites work: Natural Self-Reducible Sets
cites work: The polynomial-time hierarchy
cites work: Q3659676
cites work: NP is as easy as detecting unique solutions
description: scientific article; zbMATH DE number 4070316