Complete Problems and Strong Polynomial Reducibilities
From MaRDI portal
Publication:4016403
DOI10.1137/0221044zbMath0749.68035OpenAlexW2078896977MaRDI 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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)
Related Items (22)
One-way functions and the isomorphism conjecture ⋮ Collapsing degrees via strong computation ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ An application of the translational method ⋮ The isomorphism conjecture holds and one-way functions exist relative to an oracle ⋮ On P-immunity of exponential time complete sets ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Comparing reductions to NP-complete sets ⋮ Autoreducibility, mitoticity, and immunity ⋮ The degree structure of 1-L reductions ⋮ On lower bounds of the closeness between complexity classes ⋮ Productive functions and isomorphisms ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Non-uniform reductions ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ On sets polynomially enumerable by iteration ⋮ NP-Creative sets: A new class of creative sets in NP ⋮ On p-creative sets and p-completely creative sets ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ On 1-truth-table-hard languages ⋮ For completeness, sublogarithmic space is no space.
This page was built for publication: Complete Problems and Strong Polynomial Reducibilities
