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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.