Why is exact inference in a Bayesian network both NP-hard and P-hard?

Question

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.

Answer 1

It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard.

It appears that you have proven that it is NP-Hard, but are unsure how to show that it is also P-Hard.

This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to pick a P-Complete problem and reduce it to BN.