Complexity of clausal constraints over chains

DOI10.1007/s00224-007-9003-zzbMath1141.68034OpenAlexW2047329448MaRDI QIDQ2480746

Gernot Salzer, Miki Hermann, Nadia Creignou, Andrei A. Krokhin

Publication date: 3 April 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9003-z

zbMATH Keywords

ComplexityInequalitiesConstraint satisfaction problemsClausal patternsDichotomy theoremFinite totally ordered domains

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Unique inclusions of maximal C-clones in maximal clones ⋮ Approximability of clausal constraints ⋮ Maximal and minimal C-monoids ⋮ The number of clones determined by disjunctions of unary relations ⋮ Introduction to the Maximum Solution Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Conjunctive-query containment and constraint satisfaction
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Building tractable disjunctive constraints
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Automated Reasoning
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Tractable constraints on ordered domains