Función de complejidad adecuada

Una función de complejidad propia es una función f que asigna números naturales a números naturales de tal manera que:

• f es no decreciente ;
• Existe una máquina de Turing de k cadenas M tal que, en cualquier entrada de longitud n , M se detiene después de O( n + f ( n )) pasos, utiliza O( f ( n )) espacio y produce f ( n ) espacios en blanco consecutivos.

Si f y g son dos funciones de complejidad propias, entonces f  + g , fg y 2f ^también son funciones de complejidad propias. 

Nociones similares incluyen funciones honestas, funciones construibles en el espacio y funciones construibles en el tiempo .

Myashnikov, Alexei; Shpilrain, Vladimir; Ushakov, Vladimir (2008). Criptografía basada en grupos . Birkhauser. pág.  28. ISBN 978-3-7643-8826-3.