The complexity of probabilistic inference in multi-dimensional Bayesian classifiers

Multi-dimensional Bayesian networks (MBCs) have been recently shown to perform efficient classifications. In this study, we evaluate the computational complexity of exact inference, MAP (maximum a posterior) and MPE (most probable explanation) in MBCs. Even when MBCs have simple graphical structures under strong constraints, we find that computing exact inference is NP-Complete, while computing MAP and MPE is NP-hard.status: accepte