4 min readLogic and Knowledge
A Million Clauses, or Sixty-One
Converting one short formula to conjunctive normal form by distributing gives 1,048,576 clauses and 20,971,520 literals; naming the subformulas gives 61 clauses and 160 literals, a factor of 131,072 in literals, and loses nothing at all - the two have the same number of models, checked exhaustively. The encoding is where a satisfiability problem is won or lost, not the solver.
Artificial IntelligenceMathematics