Una función de complejidad adecuada es una función f mapeando un número natural a un número natural tal que:
Si f y g son dos funciones de complejidad propias, entonces f + g , fg y 2 f también son funciones de complejidad propias.
Conceptos similares incluyen la función honesto, la función de espacio construible , y la función de tiempo construible .