On the Structure and the Number of Prime Implicants of 2-CNFs

Abstract

Let $m(n,k)$ be the maximum number of prime implicants that any $k$-CNF on n variables can have. We show that $3^{n/3}\le m(n,2)\le (1+o(1))3^{n/3}$.