Constraints, consistency and closure
From MaRDI portal
Publication:1274280
DOI10.1016/S0004-3702(98)00022-8zbMath0909.68076MaRDI QIDQ1274280
Martin C. Cooper, Peter G. Jeavons, David A. Cohen
Publication date: 12 January 1999
Published in: Artificial Intelligence (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, Recent Results on the Algebraic Approach to the CSP, Dualities for Constraint Satisfaction Problems, Classes of submodular constraints expressible by graph cuts, The expressive rate of constraints, Periodic constraint satisfaction problems: Tractable subclasses, \(H\)-coloring dichotomy revisited, The complexity of constraint satisfaction games and QCSP, Towards a dichotomy theorem for the counting constraint satisfaction problem, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, The expressive power of valued constraints: Hierarchies and collapses, The expressive power of binary submodular functions, Existentially restricted quantified constraint satisfaction, Minimization of locally defined submodular functions by optimal soft arc consistency, Relatively quantified constraint satisfaction, Learnability of quantified formulas., Constraint propagation techniques for the disjunctive scheduling problem, An efficient algorithm for a class of constraint satisfaction problems, A new tractable class of constraint satisfaction problems, Constraint satisfaction with succinctly specified relations, Learning intersection-closed classes with signatures, Domain permutation reduction for constraint satisfaction problems, Properties of tree convex constraints, Majority constraints have bounded pathwidth duality, The complexity of soft constraint satisfaction, Efficient interval partitioning-local search collaboration for constraint satisfaction, Combinatorial problems raised from 2-semilattices, On the CSP Dichotomy Conjecture, The Expressive Power of Binary Submodular Functions, The existence of a near-unanimity term in a finite algebra is decidable, The Expressive Power of Valued Constraints: Hierarchies and Collapses
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Network-based heuristics for constraint-satisfaction problems
- An optimal k-consistency algorithm
- Temporal constraint networks
- From local to global consistency
- A generic arc-consistency algorithm and its specializations
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Consistency in networks of relations
- Constraint satisfaction over connected row-convex constraints
- Fast parallel constraint satisfaction
- Decomposing constraint satisfaction problems using database techniques
- Characterising tractable constraints
- Networks of constraints: Fundamental properties and applications to picture processing
- Constraint relaxation may be perfect
- A sufficient condition for backtrack-bounded search
- A Sufficient Condition for Backtrack-Free Search
- On binary constraint problems
- On the minimality and global consistency of row-convex constraint networks
- Closure properties of constraints
- Constraint tightness and looseness versus local and global consistency
- Monotone monadic SNP and constraint satisfaction
- The complexity of satisfiability problems
- A relational model of data for large shared data banks
- Tractable constraints on ordered domains
