Complexity of clausal constraints over chains

DOI10.1007/S00224-007-9003-ZMaRDI QIDQ2480746zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Miki Hermann, Gernot Salzer, Andrei 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

Clausal patternsComplexityConstraint satisfaction problemsDichotomy theoremFinite totally ordered domainsInequalities

Mathematics Subject Classification ID

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

Recommendations

• Approximability of clausal constraints
• The complexity of problems for quantified constraints
• The complexity of clausal fragments of LTL
• Classifying the Complexity of Constraints Using Finite Algebras
• scientific article; zbMATH DE number 1555173
• Methods and Applications of Artificial Intelligence
• The complexity of constraint satisfaction revisited
• Simplifying clausal satisfiability problems

Cites work

• Automated deduction for many-valued logics
• Automated Reasoning
• Building tractable disjunctive constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity classifications of Boolean constraint satisfaction problems
• Conjunctive-query containment and constraint satisfaction
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tractable constraints on ordered domains

Cited in

(10)

• Unique inclusions of maximal C-clones in maximal clones
• The number of clones determined by disjunctions of unary relations
• Maximal and minimal C-monoids
• Efficient Algorithms for Description Problems over Finite Totally Ordered Domains
• scientific article; zbMATH DE number 1507192 (Why is no real title available?)
• A complexity perspective on entailment of parameterized linear constraints
• Tractable constraints in finite semilattices
• Automated Reasoning
• Introduction to the Maximum Solution Problem
• Approximability of clausal constraints

This page was built for publication: Complexity of clausal constraints over chains

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