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.