Non-déterminisme

Un algorithme est non-déterministe si, à partir d'un état donné, il peut passer non pas à un seul autre état, mais à plusieurs. Ainsi, de proche en proche, il ne définira pas une séquence d'opérations, mais un arbre d'opérations possibles. Un tel mécanisme abstrait peut facilement explorer des problèmes à combinaisons multiples. Il peut être réalisé concrètement au prix, au pire, d'une complexité exponentielle.