No label defined (Q4934292)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1390027
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1390027

      Statements

      0 references
      13 July 2000
      0 references
      computable function
      0 references
      function algebra
      0 references
      computation model
      0 references
      recursion scheme
      0 references
      type 2 functional
      0 references
      survey
      0 references
      primitive recursive functions
      0 references
      complexity classes
      0 references
      quantifier hierarchies
      0 references
      A function algebra is a smallest class of functions containing some initial functions and being closed under some operations (e.g., composition of functions or primitive recursion). In 1975 Kurt Gödel envisioned a classification of all total recursive functions as a hierarchy of function algebras, allowing operations of growing complexity. The present paper surveys some work that has been done in the past decades on algebraic characterizations of subclasses of the primitive recursive functions and their relation to computational complexity theory. Some of the presented results are: a characterization of the logtime hierarchy \(\text{LH}\) (known to coincide with the constant-depth circuit class \(\text{ AC}^0\)) by an algebra \(A_0\) defined from a family of basic functions by composition and so-called concatenation recursion on notation; a characterization of \(\text{ TC}^0\) by allowing in the above multiplication as an additional initial function; a characterization of \(\text{ NC}\) by adding to the above the operation of so-called weak bounded recursion on notation; characterizations of time- and space-bounded complexity classes by algebras using the operation of bounded recursion; characterizations of quantifier hierarchies such as the linear time hierarchy or the polynomial time hierarchy using bounded minimization. Further results concern safe recursion schemes and classes of type 2 functionals. An interesting open questions that is discussed concerns the class \(\mathcal K\), defined by \textit{R. L. Constable} ``Type two computational complexity'', Proc. 5th ann.~ACM Symp.~Theor.~Comput., Austin 1973, 108-121 (1973; Zbl 0306.68022)]. In that paper it is claimed without proof that \(\mathcal K\) is the class of all polynomial-time computable functions. However, today it is suspected that this claim is wrong and the question remains to what complexity class Constable's class \(\mathcal K\) corresponds. For the entire collection see [Zbl 0923.03001].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references