On the size of minimal unsatisfiable formulas

Choongbum Lee

An unsatisfiable formula is called minimal if it becomes satisfiable whenever any of its clauses are removed. We construct minimal unsatisfiable $k$-SAT formulas with $\Omega (n^k)$ clau…