19
$\begingroup$

The first well-known $NPC$ problem is the Boolean Satisfiability Problem, which has a proof of being $NPC$ done by Cook (Cook-Levin Theorem).

The problem can easily be described the following way:

In complexity theory, the satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. So, we should give an answer 'yes' if there is a set of boolean variables which yield 'TRUE' for the given for the corresponding expression.

However, I have a question. The wikipedia article states the following:

SAT is easier if the formulas are restricted to those in disjunctive normal form, that is, they are disjunction (OR) of terms, where each term is a conjunction (AND) of literals (possibly negated variables). Such a formula is indeed satisfiable if and only if at least one of its terms is satisfiable, and a term is satisfiable if and only if it does not contain both x and NOT x for some variable x. This can be checked in polynomial time.

So, basically, if the expression is written in the DNF, this problem is not $NPC$, but simply $P$.

However, as far as I know, there is a $O(p(n))$ algorithm to transform any given boolean expression into DNF and DNF exists for any boolean expression.

What am I missing or misinterpreting? There is obviously an error in my logic, because it resulted in making the SAT problem $P$, but not $NP$.

Thank you!

$\endgroup$
1
  • $\begingroup$ This was made more clear in Wikipedia now "But it can take exponential time and space to convert a general SAT problem to disjunctive normal form." $\endgroup$
    – Fizz
    Apr 3, 2021 at 11:25

1 Answer 1

Reset to default
26
$\begingroup$

Your claim that you can convert an arbitrary formula to DNF in polynomial time is mistaken.

You can convert a boolean formula into DNF, but the resulting formula might be very much larger than the original formula—in fact, exponentially so. Since the conversion algorithm must at the very least write out the resulting DNF formula, its running time must be at least the length of the output, and therefore its worst-case running time must be exponential.

Even if you somehow finesse the issue of writing out the DNF version of the input formula, the algorithm you propose takes a formula of size $x$, converts it into a DNF formula of worst-case size $2^x$, and then calculates satisfiability of the DNF formula in time $P(2^x)$ for some polynomial $P$. This is no better in general than just trying every possible satisfying assignment in the original formula.

The Wikipedia article on "Disjunctive Normal Form" has an example of a formula that explodes when converted to DNF. But it's an easy example. Consider:

$$(A_1\lor B_1)\land(A_2\lor B_2)\land\cdots\land(A_n\lor B_n)$$

This has length proportional to $n$. But in DNF it turns into:

$$(A_1\land A_2\land\cdots\land A_n)\lor\\ (B_1\land A_2\land\cdots\land A_n) \lor \\ (A_1\land B_2\land\cdots\land A_n) \lor \\ (B_1\land B_2\land\cdots\land A_n) \lor \\ \vdots\\ (B_1\land B_2\land\cdots\land B_n)\hphantom{\lor} $$

with $2^n$ clauses.

$\endgroup$
7
  • 1
    $\begingroup$ In my intuition, it seems that "hard" SAT problems are typically sparsely satisfiable, if at all, and thus would most definitely not explode in minimal DNF form. If that's true, then the Wikipedia example may be ill-contrived for the context. $\endgroup$
    – user253804
    Jul 16, 2015 at 22:15
  • 4
    $\begingroup$ @jrodatus: The problem is that in the general case, an exponential number of intermediate terms is generated. These terms can be simplified by applying Boolean simplification rules, and the remaining DNF formula is the set of satisfying solutions. But the exponential blowup cannot be avoided unless P = NP. See: en.wikipedia.org/wiki/… $\endgroup$
    – Luke Hutchison
    Sep 3, 2016 at 8:18
  • $\begingroup$ What the deleted user was suggesting may actually be "even harder" as MIN DNF is $\Sigma_2^P$-complete sciencedirect.com/science/article/pii/S0022000001917751 $\endgroup$
    – Fizz
    Apr 2, 2021 at 14:16
  • $\begingroup$ As further noted in that paper, real-world industrial implementations of MIN DNF (e.g. Espresso) actually use TAUTOLOGY as a subroutine. So even for practical purpose, the (deleted users') suggestion is "backwards" in terms of practicality. $\endgroup$
    – Fizz
    Apr 2, 2021 at 14:48
  • $\begingroup$ @LukeHutchison. The Wikipedia article you have linked talks about exponential blowup when converting from DNF to CNF, and not the other way around. So could you provide a reference to the fact that when converting CNF to DNF, which is what the OP asks, exponential blowup cannot be avoided unless P=NP? Perhaphs you mean en.wikipedia.org/wiki/Disjunctive_normal_form? And maybe also math.stackexchange.com/questions/3113083/…? Even given these links, how does P=NP enter into the picture? Thanks. $\endgroup$
    – EGME
    Jul 30 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .