Logical compactness and constraint satisfaction problems

DOI10.23638/LMCS-13(1:1)2017MaRDI QIDQ2980963zbMATH OpenFDO

Authors Danny Rorabaugh, Claude Tardif, David Wehlau

Publication date 8 May 2017

Full work available at URL https://arxiv.org/abs/1609.05221

zbMATH Keywords

compactness theoremconstraint satisfaction problemsrelational structures

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Models with special properties (saturated, rigid, etc.) (03C50) Other combinatorial set theory (03E05) Other set-theoretic hypotheses and axioms (03E65) Relational systems, laws of composition (08A02) Applications of universal algebra in computer science (08A70) Descriptive complexity and finite models (68Q19) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: We investigate a correspondence between the complexity hierarchy of constraint satisfaction problems and a hierarchy of logical compactness hypotheses for finite relational structures. It seems that the harder a constraint satisfaction problem is, the stronger the corresponding compactness hypothesis is. At the top level, the NP-complete constraint satisfaction problems correspond to compactness hypotheses that are equivalent to the ultrafilter axiom in all the cases we have investigated. At the bottom level, the simplest constraint satisfaction problems correspond to compactness hypotheses that are readily provable from the axioms of Zermelo and Fraenkel.

Recommendations

• scientific article; zbMATH DE number 1416397
• scientific article; zbMATH DE number 1670830
• Methods and Applications of Artificial Intelligence
• A Logical Approach to Constraint Satisfaction
• Compaction, Retraction, and Constraint Satisfaction

Cites work

• Applications of product colouring
• Axiom of choice for finite sets
• Coloring infinite graphs and the Boolean prime ideal theorem
• scientific article; zbMATH DE number 3782930 (Why is no real title available?)
• The axiom of choice
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(10)

• Tight representation of logical constraints as cardinality rules
• Generalized Davis-Putnam and satisfiability problems in mathematics
• Constraint satisfaction, irredundant axiomatisability and continuous colouring
• scientific article; zbMATH DE number 1416397 (Why is no real title available?)
• AC complement problems: Satisfiability and negation elimination
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• STACS 2004
• Constraint Satisfaction, Logic and Forbidden Patterns
• CLAP: A New Algorithm for Promise CSPs
• Constraint satisfaction problems, compactness and non-measurable sets

This page was built for publication: Logical compactness and constraint satisfaction problems

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