\input zb-basic
\input zb-ioport
\iteman{io-port 05318856}
\itemau{Bordeaux, Lucas; Hamadi, Youssef; Vardi, Moshe Y.}
\itemti{An analysis of slow convergence in interval propagation.}
\itemso{Bessi\`ere, Christian (ed.), Principles and practice of constraint programming -- CP 2007. 13th international conference, CP 2007, Providence, RI, USA, September 23--27, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74969-1/pbk). Lecture Notes in Computer Science 4741, 790-797 (2007).}
\itemab
Summary: When performing interval propagation on integer variables with a large range, slow-convergence phenomena are often observed: it becomes difficult to reach the fixpoint of the propagation. This problem is practically important, as it hinders the use of propagation techniques for problems with large numerical ranges, and notably problems arising in program verification. A number of attempts to cope with this issue have been investigated, yet all of the proposed techniques only guarantee a fast convergence on specific instances. An important question is therefore whether slow convergence is intrinsic to propagation methods, or whether an improved propagation algorithm may exist that would avoid this problem. This paper proposes the first analysis of the slow convergence problem under the light of complexity results. It answers the question, by a negative result: if we allow propagators that are general enough, computing the fixpoint of constraint propagation is shown to be intractable. Slow convergence is therefore unavoidable unless $\text {P}=\text {NP}$. The result holds for the propagators of a basic class of constraints.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-74970-7\_56}
\end