1
$\begingroup$

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

So I did formulate a 3SAT Problem by defining 3CNF:

(x1 ∨ x2) ∧ (¬x3 ∨ x2) ∧ (x3 ∨ x1)

I reduced it to inference in BN , 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 O(n^c) . For NP the polynomial time cannot be determined, hence, non deterministic polynomial time. The question that scientist try to answer is whether a computer who is able to verify a solution would also be able to find a solution. P= NP ?

So basically that what I understood from my lecture, but still I am not sure how I can prove that exact inference in BN is NP-hard and P-hard.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.