Hardness
u Inference is NP-Hard; approximation is NP-Hard
uWork
on a tapestry of exact and approximate algorithms
uExploit
special structure, probe portions of model, restricted
probabilistic relationships
Eric Horvitz, April 5, 2003