3
$\begingroup$

So I recently learned about the boolean satisfaction problem in an article that linked it to super mario brothers. Anyways, I was wondering why you can't solve the problem in the following way.

  1. Write your expression in DNF.
  2. Check to see if any of the clauses (terms with ors or just variables--no ands) have just regular variables or just the negation of variables or some combination.
  3. If only one clause has just regular variables or regular variables with negation, set all booleans to 1 or 0 depdending upon whether or not it's the negation case or the regular case. This will satisfy all other clauses.
  4. If 1 clause has all regular vars, and the other all negations then it's not solvable.
  5. If none of these types occur, simply set the values all to one.

Am I missing something here?

  • 0
    ...please, contain the article or at least the reference, thanks.2012-03-21

1 Answers 1

4

"Writing in DNF" can, in some cases, extend the formula to solve exponentially. Wikipedia has an example.

  • 0
    Oh I see. That's not very good then.2012-03-21