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 of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

(37)

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

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)