The complexity of equality constraint languages

DOI10.1007/S00224-007-9083-9MaRDI QIDQ929295zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Jan Kára

Publication date 17 June 2008

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

Full work available at URL https://doi.org/10.1007/s00224-007-9083-9

zbMATH Keywords

Computational complexityConstraint satisfactionClones on infinite domainsLogic in computer science

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)

Recommendations

• The Complexity of Equality Constraint Languages
• Quantified Equality Constraints
• The Complexity of Counting Quantifiers on Equality Languages
• The complexity of counting quantifiers on equality languages
• The complexity of maximal constraint languages

Cites work

• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 836094 (Why is no real title available?)
• scientific article; zbMATH DE number 5037618 (Why is no real title available?)
• Building tractable disjunctive constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Complexity classifications of Boolean constraint satisfaction problems
• Constraint Satisfaction Problems with Infinite Templates
• Constraint Satisfaction with Countable Homogeneous Templates
• Datalog and Constraint Satisfaction with Infinite Templates
• Local and global relational consistency
• Maximal clones on uncountable sets that include all permutations
• NP is as easy as detecting unique solutions
• Reasoning about temporal relations
• The Complexity of Equality Constraint Languages
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The maximal clones on countable sets that include all permutations.
• `` Strong NP-Completeness Results

Cited in

(25)

• Tractability in constraint satisfaction problems: a survey
• Maximal infinite-valued constraint languages
• Minimal functions on the random graph
• A dichotomy for first-order reducts of unary structures
• Reconstructing the topology of clones
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• Tractable combinations of temporal CSPs
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Constraint satisfaction problems for reducts of homogeneous graphs
• Constraint satisfaction problems over numeric domains
• Constraint satisfaction problems over the integers with successor
• The complexity of quantified constraints using the algebraic formulation
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• The language of stratified sets is confluent and strongly normalising
• The Complexity of Equality Constraint Languages
• The Complexity of Counting Quantifiers on Equality Languages
• The Complexity of Abduction for Equality Constraint Languages
• General lower bounds and improved algorithms for infinite-domain CSPs
• An initial study of time complexity in infinite-domain constraint satisfaction
• The complexity of counting quantifiers on equality languages
• On the descriptive complexity of temporal constraint satisfaction problems
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Quantified Equality Constraints
• scientific article; zbMATH DE number 3874640 (Why is no real title available?)

This page was built for publication: The complexity of equality constraint languages

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