This only implies that the required computation time scales poorly with the number of graph nodes. It seems like for any reasonable number of beliefs that could be input by a single person you wouldn’t run into any practical difficulty. Perhaps if one tried to extend this to a web based application with a world-wide, constantly updated belief net you would run into scaling issues, and then you simply make practical decisions about how complex you’re willing to let things get.
Probabilistic inference for general belief networks is NP-hard (see The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks (PDF)). Thus straitforward approach is not an option. The problem is more like finding computationally tractable yet sufficiently powerful subtype of belief networks.
This only implies that the required computation time scales poorly with the number of graph nodes. It seems like for any reasonable number of beliefs that could be input by a single person you wouldn’t run into any practical difficulty. Perhaps if one tried to extend this to a web based application with a world-wide, constantly updated belief net you would run into scaling issues, and then you simply make practical decisions about how complex you’re willing to let things get.