Article ID Journal Published Year Pages File Type
417976 Discrete Applied Mathematics 2016 4 Pages PDF
Abstract

Let m(n,k)m(n,k) be the maximum number of prime implicants that any kk-CNF on nn variables can have. We show that 3n3≤m(n,2)≤(1+o(1))3n3.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the structure and the number of prime implicants of 2-CNFs
Authors
,