Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$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.
