The $\mu$ -measure as a tool for classifying computational complexity

Archive for Mathematical Logic 39 (7):515-539 (2000)
  Copy   BIBTEX

Abstract

Two simply typed term systems $\sf {PR}_1$ and $\sf {PR}_2$ are considered, both for representing algorithms computing primitive recursive functions. $\sf {PR}_1$ is based on primitive recursion, $\sf {PR}_2$ on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in $\sf {PR}_i$ , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes ${\mathcal{E}}_n$ for $n\ge 3$ , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1 $ for $ n\ge 1 $, where $ \mathcal{R}^n_i$ denotes the \emph{ $n$ th modified Heinermann class} based on $\mu$ . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by $\mu$ . By Ritchie's result, $\mathcal{R}^1_1$ characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that $\mathcal{R}^1_2$ characterises the polynomial time computable functions. Furthermore, the classes $\mathcal{R}^n_2$ and $\mathcal{R}^n_1$ coincide at and above level 2

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
An example related to Gregory’s Theorem.J. Johnson, J. F. Knight, V. Ocasio & S. VanDenDriessche - 2013 - Archive for Mathematical Logic 52 (3-4):419-434.
Degrees of difficulty of generalized r.e. separating classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
Subrecursive functions on partial sequences.Karl-Heinz Niggl - 1999 - Archive for Mathematical Logic 38 (3):163-193.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Embedding FD(ω) into {mathcal{P}_s} densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
Observables and Statistical Maps.Stan Gudder - 1999 - Foundations of Physics 29 (6):877-897.
Why is $$\mathcal{CPT}$$ Fundamental?O. W. Greenberg - 2006 - Foundations of Physics 36 (10):1535-1553.
A fixed point for the jump operator on structures.Antonio Montalbán - 2013 - Journal of Symbolic Logic 78 (2):425-438.
Classical Modal De Morgan Algebras.Sergio A. Celani - 2011 - Studia Logica 98 (1-2):251-266.

Analytics

Added to PP
2013-11-23

Downloads
12 (#929,405)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Control structures in programs and computational complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.
Mω considered as a programming language.Karl-Heinz Niggl - 1999 - Annals of Pure and Applied Logic 99 (1-3):73-92.

Add more citations