Trouble understanding why Disjunctive Normal Form is polynomial time solvable but not CNF.

Yes. DNF and CNF formulas describe the solution space in different ways. DNF formulas are explicit in that they tell you exactly which assignments will satisfy the formula. CNF formulas are implicit in that they tell you what assignments won't satisfy the formula.

Because DNF formulas are explicit, to determine satisfiability it suffices to go through the list of clauses and verify that at least one does not contain a variable and its negation. One pass through the clauses can at most require time linear to the number of clauses and quadratic to the number of variables, so there's your polynomial-time decision procedure for DNF satisfiability.

Tags:

Logic

Np Complete

Discrete Mathematics

Related

Probability of winning in a die rolling game with six players Generating functions for tail length and rho-length infinite subset of an finite set? Showing $\pi/(2\sqrt3)=1-1/5+1/7-1/11+1/13-1/17+1/19-\cdots$ Is zero the center of the numeric sequence? Number of possible combinations of x numbers that sum to y Plotting $f(x) = \sin(x)+\cos(x)$ by converting it to another form What is the difference between a Set, a Vector, and, a Vector Space? How exactly does the sign of the dot product determine the angle between two vectors? Each of the two persons makes a single throw with a pair of unbiased dice.What is the probability that the throws are equal? Let $Y$ be a finite-dimensional normed space, $X$ a normed space, and $T: X \to Y$ a surjective linear operator. Show that $T$ is an open mapping. concentration of maximum of gaussians

Recent Posts