Second International Conference of Advanced Computer Science & Information Thechnology (ACSIT-2014) edition:2 location:Zurich date:June 14-15
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.