On the Structure and the Number of Prime Implicants of 2-CNFs
classification
💻 cs.DM
math.CO
keywords
implicantsnumberprimecnfsmaximumstructurevariables
read the original 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}$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.