# Convert conjunctive normal form to equivalent boolean formula with only NOR gates

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?

• Does mentioning "Symbol complexity" in the title is irrelevant? – Farewell Stack Exchange Aug 6 '17 at 18:18
• 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. – D.W. Aug 6 '17 at 18:50
• Got it. See my comment there. – Farewell Stack Exchange Aug 6 '17 at 18:56