## Abstract

Many problems and applications can be naturally modelled and solved using constraints with more than two variables. Such n-ary constraints, in particular, arithmetic constraints are provided by many finite domain constraint programming systems. The best known worst case time complexity of existing algorithms (GAC-schema) for enforcing arc consistency on general CSPs is O(ed^{n}) where d is the size of domain, e is the number of constraints and n is the maximum number of variables in a single constraint. We address the question of efficient consistency enforcing for n-ary constraints. An observation here is that even with a restriction of n-ary constraints to linear constraints, arc consistency enforcing is NP-complete. We identify a general class of monotonic n-ary constraints (which includes linear inequalities as a special case). Such monotonic constraints can be made arc consistent in time O(en^{3}d). The special case of linear inequalities can be made arc consistent in time O(en^{2}d) using bounds-consistency which exploits special properties of the projection function.

Original language | English |
---|---|

Pages (from-to) | 470-483 |

Number of pages | 14 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 1894 |

State | Published - 2000 |