Complete problems and strong polynomial reducibilities

DOI10.1007/BFB0028988MaRDI QIDQ5096158zbMATH OpenOpenAlexFDO

Authors

Publication date 16 August 2022

Published in STACS 89 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0028988

zbMATH Keywords

complexity classpolynomial timerecursion theoremTuring machine

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)

Cites work

• scientific article; zbMATH DE number 3984574 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On Isomorphisms and Density of NP and Other Complete Sets
• On one-one polynomial time equivalence relations
• On one-way functions and polynomial-time isomorphisms

Cited in

(6)

• A solution to Curry and Hindley's problem on combinatory strong reduction
• Exponential-time and subexponential-time sets
• DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
• Completeness and reduction in algebraic complexity theory
• Barendregt's problem \#26 and combinatory strong reduction
• 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 Q5096158)