função de complexidade adequada - Proper complexity function
Uma função complexidade adequada é uma função de f mapeando um número natural de um número natural de tal forma que:
- f é não decrescente;
- existe um k -string Turing máquina M de tal modo que em qualquer entrada de comprimento n , M interrompe depois de O ( n + f ( n )) passos, utiliza O ( f ( n )) do espaço, e emite f ( n ) espaços em branco consecutivos .
Se f e g são duas funções adequadas complexidade, então f + g , fg , e 2 f , são também funções de complexidade adequadas.
Noções semelhantes incluem a função honesto, função espaço-constructible e função Time-constructible .
