# DNF and CNF and Complexity Theory

$$F(z_1,...,z_n)$$ is a Boolean expression. The assignment of variable ($$x_1,...,x_n \in {0, 1}$$) is the answer of $$F$$, if $$F$$ for that assignment equals to $$1$$.

If that case is true and the conditions are met, then both of them are considered to be NP-Hard.

A) The number of answers of $$F$$ in $$DNF$$ format.

B) The number of answers of $$F$$ in $$CNF$$ format.

DNF and CNF are HERE

Can anyone describe to me in clear, simple, and concise words why both of them are true?

Counting the number of satisfying assignments to $$F$$ is at least as hard as determining whether there is a satisfying assignment. (If the count is 0, there are no satisfying assignments; if the count is $$\ge 1$$, there is a satisfying assignment.)

For CNF formulas, testing whether there is a satisfying assignment is the SAT problem, which is a classic example of a NP-hard problem.

Counting the number of satisfying assignments of $$F$$ is at least as hard as determining whether all assignments satisfy $$F$$. For DNF formulas, this is NP-hard, too.

• am I true? we search for number of answer that assignment is 1 in a formula, equal to we search for all satisfiable case for that formula? Dec 3 '20 at 16:34