# Is converting boolean formulas to sum-of-products a hard problem?

My reasoning is as follows.

1. Every boolean formula can be expressed as a sum-of-products.
2. Every sum-of-produts is a list of minterms.
3. For each minterm, there is 1 combination of inputs that satisfy the formula.

So if I have the sum-of-products representation of a boolean formula I can tell if it satisfiable.

But that is the SAT problem, which is hard.

So the hard part of the 3 step procedure above must be transforming a boolean formula into a sum of products.

Is this reasoning right?

• "sum-of-products" in the sense of GF(2), or in the sense of the Boolean interpretation of those operations? ​ ​ ​
– user12859
Sep 23 '16 at 20:52
• I mean going from (AB)+C to ABC'+ABC+ACB+ACB', which tells us there are 4 solutions to the problem. (If i am correct). Sep 23 '16 at 20:53
• Is ABC+ACB a typo? ​ ​
– user12859
Sep 23 '16 at 20:55
• Possible duplicate: Proving that the conversion from CNF to DNF is NP-Hard
– Raphael
Sep 23 '16 at 21:28
• Possibly related: this, this and this
– Raphael
Sep 23 '16 at 21:29