2

I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem.

So, I did formulate a 3-SAT problem by defining 3-CNF:

$$(x_1 \lor x_2) \land (\neg x_3 \lor x_2) \land (x_3 \lor x_1)$$

I reduced it to inference in a Bayesian network, and produced all conditional probabilities, and I know which variable assignment would lead for the entire expression to be true.

I am aware of the difference between P and NP. (Please correct me if I am wrong):

Any P problem with an input of the size $n$ can be solved in $\mathcal{O}(n^c)$. For NP, the polynomial-time cannot be determined, hence, nondeterministic polynomial time. The question that scientists try to answer is whether a computer who is able to verify a solution would also be able to find a solution. P= NP?

However, I am still not sure how I can prove that exact inference in Bayesian network is NP-hard and P-hard.