C'est-à-dire que le temps requis pour résoudre le problème en utilisant n'importe quel algorithme actuellement connu augmente très rapidement à mesure que la taille du problème augmente.
Très souvent, le temps ou l'effort requis pour résoudre un tel problème augmente avec l'ampleur du problème.