Complete Problems and Strong Polynomial Reducibilities
From MaRDI portal
Publication:4016403
DOI10.1137/0221044zbMATH Open0749.68035OpenAlexW2078896977MaRDI QIDQ4016403FDOQ4016403
Authors:
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
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (34)
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes
- On one-one polynomial time equivalence relations
- On p-creative sets and p-completely creative sets
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- A comparison of polynomial time completeness notions
- Comparing reductions to NP-complete sets
- On 1-truth-table-hard languages
- For completeness, sublogarithmic space is no space.
- An application of the translational method
- Introduction to Autoreducibility and Mitoticity
- Non-uniform reductions
- NP-Creative sets: A new class of creative sets in NP
- Autoreducibility, mitoticity, and immunity
- Collapsing degrees via strong computation
- A solution to Curry and Hindley's problem on combinatory strong reduction
- Productive functions and isomorphisms
- Strong nondeterministic Turing reduction - a technique for proving intractability
- A note on complete problems for complexity classes
- Title not available (Why is that?)
- One-way functions and the isomorphism conjecture
- The degree structure of 1-L reductions
- Completeness and reduction in algebraic complexity theory
- Observations on complete sets between linear time and polynomial time
- Reductions among polynomial isomorphism types
- On sets polynomially enumerable by iteration
- Barendregt's problem \#26 and combinatory strong reduction
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Separating NE from some nonuniform nondeterministic complexity classes
- Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
- On P-immunity of exponential time complete sets
- One-way functions and the nonisomorphism of NP-complete sets
- On lower bounds of the closeness between complexity classes
- Title not available (Why is that?)
- Strong polynomial-time reducibility
This page was built for publication: Complete Problems and Strong Polynomial Reducibilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4016403)
