Constraint satisfaction problems over the integers with successor

DOI10.1007/978-3-662-47672-7_21zbMATH Open1440.68111arXiv1503.08572OpenAlexW1813610230MaRDI QIDQ3448790FDOQ3448790

Authors: Manuel Bodirsky, Barnaby Martin, Antoine Mottet 

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over $(BbbZ,<)$. Our main result says that every distance CSP is in Ptime or NP-complete, unless it can be formulated as a finite domain CSP in which case the computational complexity is not known in general.

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

Recommendations

• Discrete temporal constraint satisfaction problems
• Constraint satisfaction problems over numeric domains
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Cites Work

• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• On the scope of the universal-algebraic approach to constraint satisfaction
• Title not available (Why is that?)
• Constraint Satisfaction with Countable Homogeneous Templates
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Title not available (Why is that?)
• Closure properties of constraints
• Model Theory
• The complexity of constraint satisfaction: an algebraic approach
• Computational complexity of linear constraints over the integers
• The complexity of equality constraint languages

Cited In (13)

• Constraint Satisfaction Problems on Intervals and Lengths
• Title not available (Why is that?)
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• MAX-closed semilinear constraint satisfaction
• Tropically convex constraint satisfaction
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• A dichotomy for first-order reducts of unary structures
• Constraint satisfaction problems over numeric domains
• The wonderland of reflections
• The language of stratified sets is confluent and strongly normalising
• \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
• Discrete temporal constraint satisfaction problems

This page was built for publication: Constraint satisfaction problems over the integers with successor

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