Les algorithmes mis en place pour effectuer de telles optimisations sont structurellement combinatoires. La littérature nous fournit notamment la preuve de la NP-Complétude d'un "sous-problème" (qui est nécessaire pour les phases de normalisation et de factorisation): le pattern-matching Associatif Commutatif [4].