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.