Complete Problems and Strong Polynomial Reducibilities

DOI10.1137/0221044MaRDI QIDQ4016403zbMATH OpenOpenAlexFDO

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)

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