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
• would you please answer my comments? Dec 4 '20 at 9:28
• @LisaBerry, I don't understand your question, so I don't know how to answer it. Sorry.
– D.W.
Dec 4 '20 at 20:19
• what is the meaning of "number of answers"? means all cases of assignment of variable that formula being satisfy? Dec 4 '20 at 20:25
• @LisaBerry, You used that phrase, not me. I assume it means "number of satisfying assignments". Only you can know whether that's what you meant or not.
– D.W.
Dec 4 '20 at 20:26