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.


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.


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.