  MAP is the problem of finding a most probable instantiation of a set of
variables given evidence. MAP has always been perceived to be significantly
harder than the related problems of computing the probability of a variable
instantiation Pr, or the problem of computing the most probable explanation
(MPE). This paper investigates the complexity of MAP in Bayesian networks.
Specifically, we show that MAP is complete for NP^PP and provide further
negative complexity results for algorithms based on variable elimination. We
also show that MAP remains hard even when MPE and Pr become easy. For example,
we show that MAP is NP-complete when the networks are restricted to polytrees,
and even then can not be effectively approximated. Given the difficulty of
computing MAP exactly, and the difficulty of approximating MAP while providing
useful guarantees on the resulting approximation, we investigate best effort
approximations. We introduce a generic MAP approximation framework. We provide
two instantiations of the framework; one for networks which are amenable to
exact inference Pr, and one for networks for which even exact inference is too
hard. This allows MAP approximation on networks that are too complex to even
exactly solve the easier problems, Pr and MPE. Experimental results indicate
that using these approximation algorithms provides much better solutions than
standard techniques, and provide accurate MAP estimates in many cases.
