Complejidad computacional y álgebra de funciones

Abstract

Usually, computational complexity classes are given explicitly using computation models and certain restrictions on available resources (time and/or space). However, in many cases, it is possible to obtain alternative descriptions of these classes as algebras of functions. In this work, some results of this type are presented. Logarithmic and lineal time hierarchies are characterized by functions algebras. We also present some functions algebras for polynomial time, logarithmic space and linear space complexity classes.

Las clases de complejidad computacional suelen darse de manera explícita mediante modelos de computación y ciertas restricciones sobre los recursos disponibles (normalmente tiempo y/o espacio). Sin embargo, en muchos casos, es posible obtener descripciones alternativas de dichas clases como álgebras de funciones. En este trabajo se presentan algunos resultados de este tipo, caracterizando mediante álgebras de funciones las jerarquías de tiempo logarítmico y tiempo lineal, y las clases de complejidad de tiempo polinomial, espacio logarítmico y espacio lineal.