The
$\mu$-measure as a tool for classifying computational complexity |
| |
Authors: | Karl-Heinz Niggl |
| |
Institution: | Technische Universit?t Ilmenau, Fakult?t für Informatik und Automatisierung, Fachgebiet Komplexit?tstheorie, PF 100565, 98684 Ilmenau, Germany. e-mail: niggl@theoinf.tu-ilmenau.de, DE
|
| |
Abstract: | Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , 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 for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . 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 . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented,
showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2.
Received: 22 September 1997 / Revised version: 12 May 1999 |
| |
Keywords: | Mathematics Subject Classification (2000): 03D15 03D20 68Q15 68Q42 |
本文献已被 SpringerLink 等数据库收录! |
|