Definition. Exponential Blow up problem [000m]

When converting a formula to Disjunctive Normal Form (DNF) or Conjunctive Normal Form (CNF), the size of the resulting formula can grow exponentially in the worst case. This is known as the exponential blow up problem. For example, a formula with \(n\) variables can result in a DNF or CNF with up to \(2^n\) clauses.