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

Question

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?

Answer 1

Your reasoning is correct. Your "sum-of-products" is more commonly known as disjunctive normal form (DNF). It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so converting from general Boolean formulas to DNF can't be any easier.