Tractability of exact inference

Question 1

Is exact inference intractable?

Answer 1

For polytrees (at most 1 undirected path between any two nodes in the network), the time and space complexity of the exact inference is linear in the size of the network (number of CPT entries). For non-polytrees or multiply connected networks, exact inference techniques like variable inference has exponential time and space complexity.