  Bound propagation is an important Artificial Intelligence technique used in
Constraint Programming tools to deal with numerical constraints. It is
typically embedded within a search procedure ("branch and prune") and used at
every node of the search tree to narrow down the search space, so it is
critical that it be fast. The procedure invokes constraint propagators until a
common fixpoint is reached, but the known algorithms for this have a
pseudo-polynomial worst-case time complexity: they are fast indeed when the
variables have a small numerical range, but they have the well-known problem of
being prohibitively slow when these ranges are large. An important question is
therefore whether strongly-polynomial algorithms exist that compute the common
bound consistent fixpoint of a set of constraints. This paper answers this
question. In particular we show that this fixpoint computation is in fact
NP-complete, even when restricted to binary linear constraints.
