A decidable characterization of the classes between lintime and exptime
From MaRDI portal
Publication:1045888
DOI10.1016/j.ipl.2005.09.005zbMath1185.68348OpenAlexW2065556835MaRDI QIDQ1045888
Publication date: 18 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.09.005
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- A new recursion-theoretic characterization of the polytime functions
- A foundational delineation of poly-time
- A predicative and decidable characterization of the polynomial classes of languages
- A predicative approach to the classification problem
- SAFE TURING MACHINES, GRZEGORCZYK CLASSES AND POLYTIME
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item