Fonction de complexité appropriée - Proper complexity function
Une fonction de complexité appropriée est une fonction f mappant un entier naturel à un entier naturel tel que:
- f ne diminue pas;
- il existe une machine de Turing à k chaînes M telle que sur toute entrée de longueur n , M s'arrête après O ( n + f ( n )) étapes, utilise l' espace O ( f ( n )) et produit f ( n ) blancs consécutifs .
Si f et g sont deux fonctions de complexité propres, alors f + g , fg et 2 f sont également des fonctions de complexité appropriées.
Notions similaires comprennent la fonction honnête, fonction espace constructible et fonction du temps constructible .
