<div>
It seems more difficult than I thought. Could you (or someone else) write out this CNF? I'm not sure if I could work it all out (maybe with the help of Google but that would take time), but all I really want is one such CNF. (points increased).
</div>


It seems more difficult than I thought. Could you (or someone else) write out this CNF? I'm not sure if I could work it all out (maybe with the help of Google but that would take time), but all I really want is one such CNF. (points increased).

<div>
Never mind. A conjunction of parity functions is not so difficult.<br />
+ = or<br />
* = and<br />
! = not<br />
<br />
(a+b) * (!a+!b) * (c+d) * (!c+!d) * (e+f) * (!e+!f)<br />
<br />
And (ofcourse) is blows up indeed.
</div>


Never mind. A conjunction of parity functions is not so difficult.
+ = or
* = and
! = not

(a+b) * (!a+!b) * (c+d) * (!c+!d) * (e+f) * (!e+!f)

And (ofcourse) is blows up indeed.

<div>
<div class="content wysiwyg-content">
I am looking for a small (about 5 atoms/variables) and simple CNF (Conjunctive Normal Form) expression that (obviously?) blows up exponentially when converting to DNF. There should be no equivalent DNF that is small. I know that the CNF I am looking for exists.
</div>
</div>


I am looking for a small (about 5 atoms/variables) and simple CNF (Conjunctive Normal Form) expression that (obviously?) blows up exponentially when converting to DNF. There should be no equivalent DNF that is small. I know that the CNF I am looking for exists.

CNF-&gt;DNF: exponential blowup?

The Math / Science topic primarily includes discussions of mathematics, physics, statistics and economic analysis, but also biology, chemistry and other sciences.

CNF-&gt;DNF: exponential blowup?

CNF->DNF: exponential blowup?