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.


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .