A new tractable class of constraint satisfaction problems

DOI10.1007/S10472-005-1810-9MaRDI QIDQ1776199zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau

Publication date 20 May 2005

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-005-1810-9

zbMATH Keywords

complexityconstraint satisfaction problempara-primal algebrapara-primal problems

Mathematics Subject Classification ID

Classical propositional logic (03B05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Classifying the Complexity of Constraints Using Finite Algebras
• scientific article; zbMATH DE number 1670830
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• New tractable classes from old
• Asking the Metaquestions in Constraint Tractability

Cites work

• A generic arc-consistency algorithm and its specializations
• A sufficient condition for backtrack-bounded search
• Characterising tractable constraints
• Closure properties of constraints
• Combinatorial problems raised from 2-semilattices
• Consistency in networks of relations
• Constraint relaxation may be perfect
• Constraints, consistency and closure
• Decomposing constraint satisfaction problems using database techniques
• Fast parallel constraint satisfaction
• Homogeneous operations and homogeneous algebras
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 3819803 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 1944123 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• Learnability of quantified formulas.
• Network-based heuristics for constraint-satisfaction problems
• Networks of constraints: Fundamental properties and applications to picture processing
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the minimality and global consistency of row-convex constraint networks
• Para primal algebras
• Plain para primal algebras
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tractable constraints on ordered domains

Cited in

(17)

• Testing for edge terms is decidable
• Tractability in constraint satisfaction problems: a survey
• Tractable Clones of Polynomials over Semigroups
• scientific article; zbMATH DE number 5575002 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes
• A new approach to partial constraint satisfaction problems
• Parameterized complexity of the workflow satisfiability problem
• Quantified Constraints in Twenty Seventeen
• Automata, Languages and Programming
• Recent Results on the Algebraic Approach to the CSP
• Introduction to the Maximum Solution Problem
• Recent Advances in Constraints
• On the constant-factor approximability of minimum cost constraint satisfaction problems
• Periodic constraint satisfaction problems: Tractable subclasses
• The complexity of constraint satisfaction games and QCSP
• Towards a dichotomy theorem for the counting constraint satisfaction problem

This page was built for publication: A new tractable class of constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1776199)