Complexity hierarchies derived from reduction functions

DOI10.1007/978-1-4020-2776-5_1MaRDI QIDQ7227667zbMATH OpenFDO

Authors Benedikt Löwe

Publication date 10 April 2026

Full work available at URL https://doi.org/10.1007/978-1-4020-2776-5_1

zbMATH Keywords

axiom systemeffective algorithmPeano arithmeticreduction functiontheoretical computer science

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Complexity of computation (including implicit computational complexity) (03D15) Other Turing degree structures (03D28) Hierarchies of computability and definability (03D55) Descriptive set theory (03E15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Complexity hierarchies derived from reduction functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7227667)