Complete problems and strong polynomial reducibilities

DOI10.1007/BFb0028988zbMath1492.68055OpenAlexW1496899201MaRDI QIDQ5096158

No author found.

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

Turing machinepolynomial timerecursion theoremcomplexity class

Mathematics Subject Classification ID

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

Related Items

DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ Exponential-time and subexponential-time sets

Cites Work

• On one-one polynomial time equivalence relations
• On one-way functions and polynomial-time isomorphisms
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complete problems and strong polynomial reducibilities