Complexité

Soit un $\mathcal{CSP}$ ayant $n$ variables, $m$ contraintes et dont la taille maximale des domaines est $A$, la taille d'un domaine étant le nombre de flottants qu'il contient. Alors la 2B-consistance s'exécute en $\Theta(Am)$ au pire des cas et la 3B en $\Theta(A^2n^2m)$. Le nombre de flottants dans un domaine étant en général très grand, ces méthodes sont inutilisables quand la complexité expérimentale converge vers la complexité théorique au pire des cas.