"Simple" means that propagations take only polynomial time; the combinatorics is in the distribution steps alone.
it can still happen that a search tree of exponential size has to be explored, but the time spent on propagation in each of its node is only polynomial.