NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-02-128

2002-128
On Consistency and Width Notions for Constraint Programs with Algebraic Constraints

Klaus Meer

ABSTRACT

Width notions have been studied for constraint satisfaction problems in order to exhibit subclasses of problems which allow backtrack-free solution algorithms. Among the most prominent such notions is the tree-width of the constraint graph studied, for example, by Freuder. However, Freuder's results heavily rely on constraint programs over finite domains, where each constraint is given as a list of admissible tuples and therefore fails,
for example, if continuous domains are considered.
Faltings introduced an arc consistency notion for constraints
over continuous domains that are given in a more complicated form using formulas $c(x,y) \geq 0$ for continuously differentiable functions $c.$ He then showed for such
binary constraints how arc consistency can be established and guarantees solvability of tree-structured problems.

In this paper we want to study a generalization of Freuder's and Faltings' notions to problems with algebraic constraints. We show that an analog notion of $k$-consistency
guarantees backtrack-free solution algorithms for tree-structured problems, but argue that already for binary constraints and a tree as structure of the constraint graph there arise unavoidable complexity problems in achieving $k$-consistency.
We then propose a new width notion based on previous work by Makowsky and Meer which in certain situations even allows to include global constraints without yielding a complexity explosion - something not true within the above mentioned setting.

Download Postscript