0
$\begingroup$

$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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – Lisa Berry Dec 3 '20 at 16:34
  • $\begingroup$ would you please answer my comments? $\endgroup$ – Lisa Berry Dec 4 '20 at 9:28
  • $\begingroup$ @LisaBerry, I don't understand your question, so I don't know how to answer it. Sorry. $\endgroup$ – D.W. Dec 4 '20 at 20:19
  • $\begingroup$ what is the meaning of "number of answers"? means all cases of assignment of variable that formula being satisfy? $\endgroup$ – Lisa Berry Dec 4 '20 at 20:25
  • $\begingroup$ @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. $\endgroup$ – D.W. Dec 4 '20 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.