Question

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NAND gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top