Complete Problems and Strong Polynomial Reducibilities

DOI10.1137/0221044zbMATH0749.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

zbMATH Keywords

completenesspolynomial reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Polynomial-time isomorphism of 1-L-complete sets
• A note on complete problems for complexity classes
• Reductions among polynomial isomorphism types
• Isomorphisms and 1-L reductions
• scientific article; zbMATH DE number 3984574

Cited in

(34)

• A comparison of polynomial time completeness notions
• Comparing reductions to NP-complete sets
• On 1-truth-table-hard languages
• The degree structure of 1-L reductions
• Observations on complete sets between linear time and polynomial time
• Non-uniform reductions
• A note on complete problems for complexity classes
• scientific article; zbMATH DE number 3922634 (Why is no real title available?)
• Barendregt's problem \#26 and combinatory strong reduction
• An application of the translational method
• Introduction to autoreducibility and mitoticity
• scientific article; zbMATH DE number 3984574 (Why is no real title available?)
• Productive functions and isomorphisms
• One-way functions and the isomorphism conjecture
• Separating NE from Some Nonuniform Nondeterministic Complexity Classes
• Autoreducibility, mitoticity, and immunity
• Collapsing degrees via strong computation
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• Strong polynomial-time reducibility
• On lower bounds of the closeness between complexity classes
• On one-one polynomial time equivalence relations
• Reductions among polynomial isomorphism types
• Completeness and reduction in algebraic complexity theory
• On P-immunity of exponential time complete sets
• A solution to Curry and Hindley's problem on combinatory strong reduction
• For completeness, sublogarithmic space is no space.
• On sets polynomially enumerable by iteration
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• NP-Creative sets: A new class of creative sets in NP
• One-way functions and the nonisomorphism of NP-complete sets
• Separating NE from some nonuniform nondeterministic complexity classes
• On p-creative sets and p-completely creative sets
• Strong nondeterministic Turing reduction - a technique for proving intractability
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

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)