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 NOR 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 NOR gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?

  • $\begingroup$ Does mentioning "Symbol complexity" in the title is irrelevant? $\endgroup$ Commented Aug 6, 2017 at 18:18
  • 1
    $\begingroup$ Now that you've seen the solution to cs.stackexchange.com/q/79739/755, you should be able to work out the solution to this question as well, by applying similar ideas. $\endgroup$
    – D.W.
    Commented Aug 6, 2017 at 18:50
  • $\begingroup$ Got it. See my comment there. $\endgroup$ Commented Aug 6, 2017 at 18:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.