1.Previous
3.Next

DNF of the e.g. formula has conjunctions.

Computational complexity

The Boolean satisfiability problem on conjunctive normal form formulas is NP-complete. By the duality principle, so is the falsifiability problem on DNF formulas. Therefore, it is co-NP-hard to decide if a DNF formula

1.Previous
3.Next