Exercise 14.19 [bncomplexityexercise]
Investigate the complexity of exact inference in general Bayesian networks:

Prove that any 3SAT problem can be reduced to exact inference in a Bayesian network constructed to represent the particular problem and hence that exact inference is NPhard. (Hint: Consider a network with one variable for each proposition symbol, one for each clause, and one for the conjunction of clauses.)

The problem of counting the number of satisfying assignments for a 3SAT problem is #Pcomplete. Show that exact inference is at least as hard as this.
Answer
Improve This Solution
View Answer