Algebraic Characterization of Computable and Complexity-Theoretic Analysis

Slides

In this presentation we will talk about algebraic characterization of computable and complexity-theoretic classes of real functions. Analog computation in the context of recursive analysis has been introduced by Turing [1936] in 1936, and in 1955 Grzegorczyk [1955] and Lacombe [1955]. The model used is Type 2 Turing machine which is a classical Turing machine equipped with oracles that provide finite approximations of the real arguments. There are several representations of real numbers such as Cauchy sequences, binary expansions, and left cuts. Recursively-wise they are all equivalent, however, they differ on the sub-recursive as well as the complexity-theoretic level. We adopt fast converging Cauchy sequences of dyadic rationals.

Function algebras provide machine-independent resource-free algebraic characterization of computability and complexity-theoretic classes. Many discrete computability and complexity classes have been characterized by function algebras. Most notably is the characterization of polynomial time in the work of Bellantoni and Cook; they allowed two types of function arguments: normal and safe. Safe arguments are restricted in their contribution to the computation and growth of function values and are used to give predicative form of controlled recursion. This idea has been also used to characterize the polynomial hierarchy, linear space, and some circuit classes. Real computability classes have also been algebraically characterized in analogy with discrete classes. However, to the best of my knowledge, real complexity classes have not yet been algebraically investigated. This is the project currently being pursued by O. Bournez, E. Hainry, and myself.

References

Bellantoni and Cook [1992]

S. Bellantoni and S. Cook. A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity, 2: 97–110, 1992.

Bournez and Hainry [2006]

O. Bournez and E. Hainry. Recursive Analysis Characterized as a Class of Real Recursive Functions. Fundamenta Informaticae, 74 (4): 409–433, 2006.

Campagnolo [2001]

M. Campagnolo. Computational complexity of real valued recursive functions and analog circuits. PhD thesis, Instituto Superior Técnico, 2001.

Clote [1995]

P. Clote. Logic and Computational Complexity, volume 960 of Lecture Notes in Computer Science, chapter Computation models and function algebras, pages 98–130. Springer Berlin / Heidelberg, 1995.

Grzegorczyk [1955]

A. Grzegorczyk. Computable functionals. Fundamenta Mathematicae, 42: 168–202, 1955.

Ko [1991]

K. Ko. Complexity Theory of Real Functions. Birkhäuser, 1991.

Lacombe [1955]

D. Lacombe. Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles III. Comptes Rendus de l’Académie des sciences Paris, 241: 151–153, 1955.

Turing [1936]

A. Turing. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (42): 230–265, 1936. (correction ibid. 43, pp 544-546, 1937).

Weihrauch [2000]

K. Weihrauch. Computable Analysis: An Introduction. Springer, 1 edition, 2000.

This document was translated from L^AT_EX by H^EV^EA.