Closure properties of constraints
From MaRDI portal
Publication:4376981
DOI10.1145/263867.263489zbMath0890.68064MaRDI QIDQ4376981
Marc Gyssens, Peter G. Jeavons, David A. Cohen
Publication date: 17 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Basics of Galois Connections, Recent Results on the Algebraic Approach to the CSP, Introduction to the Maximum Solution Problem, Fanout limitations on constraint systems, Tractable structures for constraint satisfaction with truth tables, Quantified constraint satisfaction and the polynomially generated powers property, Hypertree decompositions and tractable queries, Recognizing frozen variables in constraint satisfaction problems, The expressive rate of constraints, Periodic constraint satisfaction problems: Tractable subclasses, \(H\)-coloring dichotomy revisited, Hard constraint satisfaction problems have hard gaps at location 1, The complexity of constraint satisfaction games and QCSP, Towards a dichotomy theorem for the counting constraint satisfaction problem, On Boolean primitive positive clones, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, The expressive power of valued constraints: Hierarchies and collapses, Approximability of clausal constraints, Generalized modal satisfiability, Existentially restricted quantified constraint satisfaction, Affine systems of equations and counting infinitary logic, Maximal infinite-valued constraint languages, The complexity of satisfiability problems: Refining Schaefer's theorem, Minimization of locally defined submodular functions by optimal soft arc consistency, Relatively quantified constraint satisfaction, The SAT-UNSAT transition for random constraint satisfaction problems, Homogeneous and strictly homogeneous criteria for partial structures, A combinatorial constraint satisfaction problem dichotomy classification conjecture, Constraints, consistency and closure, Learnability of quantified formulas., A comparison of structural CSP decomposition methods, Fixed-parameter complexity in AI and nonmonotonic reasoning, An efficient algorithm for a class of constraint satisfaction problems, A new tractable class of constraint satisfaction problems, The complexity of minimal satisfiability problems, The complexity of problems for quantified constraints, Isomorphic implication, Domain permutation reduction for constraint satisfaction problems, Properties of tree convex constraints, On digraph coloring problems and treewidth duality, Majority constraints have bounded pathwidth duality, The complexity of soft constraint satisfaction, Combinatorial problems raised from 2-semilattices, The complexity of partition functions, Unnamed Item, On Maltsev Digraphs, On the CSP Dichotomy Conjecture, Constraint Satisfaction Parameterized by Solution Size, Approximability of the Maximum Solution Problem for Certain Families of Algebras, CSP dichotomy for special triads
