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 Answer 1

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, 2020 at 16:34
  • $\begingroup$ would you please answer my comments? $\endgroup$
    – Lisa Berry
    Dec 4, 2020 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, 2020 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, 2020 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, 2020 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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