Algebraic Characterization of Computable and Complexity-Theoretic AnalysisWalid GomaaINRIA, LORIA, 615 Rue du J. Botanique, CS 20101, Bât Eq. CARTE, 54603 Villers-les-Nancy |
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.
This document was translated from LATEX by HEVEA.