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

ComplexityInequalitiesConstraint satisfaction problemsClausal patternsDichotomy theoremFinite totally ordered domains

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• Automated Reasoning
• Automated deduction for many-valued logics
• 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
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• Tractable constraints on ordered domains

Cited in

(10)

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

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)