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

Peano arithmeticaxiom systemtheoretical computer scienceeffective algorithmreduction function

Mathematics Subject Classification ID

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

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)