Complete Problems and Strong Polynomial Reducibilities
From MaRDI portal
Publication:4016403
DOI10.1137/0221044zbMath0749.68035MaRDI QIDQ4016403
No author found.
Publication date: 14 December 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221044
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D25: Recursively (computably) enumerable sets and degrees
Related Items
An application of the translational method, Productive functions and isomorphisms, NP-Creative sets: A new class of creative sets in NP, On sets polynomially enumerable by iteration, On p-creative sets and p-completely creative sets, On 1-truth-table-hard languages, One-way functions and the isomorphism conjecture, The isomorphism conjecture holds and one-way functions exist relative to an oracle, On P-immunity of exponential time complete sets, Collapsing degrees via strong computation, On lower bounds of the closeness between complexity classes