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

preprint2015arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.