Investigate the complexity of exact inference
in general Bayesian networks:
1. Prove that any 3-SAT problem can be reduced to exact inference in a Bayesian network constructed to represent the particular problem and hence that exact inference is NP-hard. (Hint: Consider a network with one variable for each proposition symbol, one for each clause, and one for the conjunction of clauses.)
2. The problem of counting the number of satisfying assignments for a 3-SAT problem is \#P-complete. Show that exact inference is at least as hard as this.
1. Prove that any 3-SAT problem can be reduced to exact inference in a Bayesian network constructed to represent the particular problem and hence that exact inference is NP-hard. (Hint: Consider a network with one variable for each proposition symbol, one for each clause, and one for the conjunction of clauses.)
2. The problem of counting the number of satisfying assignments for a 3-SAT problem is \#P-complete. Show that exact inference is at least as hard as this.
Investigate the complexity of exact inference
in general Bayesian networks:
1. Prove that any 3-SAT problem can be reduced to exact inference in a
Bayesian network constructed to represent the particular problem and
hence that exact inference is NP-hard. (Hint:
Consider a network with one variable for each proposition symbol,
one for each clause, and one for the conjunction of clauses.)
2. The problem of counting the number of satisfying assignments for a
3-SAT problem is \#P-complete. Show that exact inference is at least
as hard as this.