4 min de lectureLogique et connaissances
Un million de clauses, ou soixante et une
Convertir une formule courte en forme normale conjonctive par distribution donne 1 048 576 clauses et 20 971 520 littéraux ; nommer les sous-formules en donne 61 et 160, soit un facteur 131 072 sur les littéraux, et ne perd rien du tout : les deux ont le même nombre de modèles, vérifié par énumération. C’est le codage, et non le solveur, qui décide du sort d’un problème de satisfiabilité.
Intelligence artificielleMathématiques