Manuel Bodirsky ; Johannes Greiner - The Complexity of Combinations of Qualitative Constraint Satisfaction Problems

lmcs:5481 - Logical Methods in Computer Science, February 20, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:21)2020
The Complexity of Combinations of Qualitative Constraint Satisfaction ProblemsArticle

Authors: Manuel Bodirsky ; Johannes Greiner

    The CSP of a first-order theory $T$ is the problem of deciding for a given finite set $S$ of atomic formulas whether $T \cup S$ is satisfiable. Let $T_1$ and $T_2$ be two theories with countably infinite models and disjoint signatures. Nelson and Oppen presented conditions that imply decidability (or polynomial-time decidability) of $\mathrm{CSP}(T_1 \cup T_2)$ under the assumption that $\mathrm{CSP}(T_1)$ and $\mathrm{CSP}(T_2)$ are decidable (or polynomial-time decidable). We show that for a large class of $\omega$-categorical theories $T_1, T_2$ the Nelson-Oppen conditions are not only sufficient, but also necessary for polynomial-time tractability of $\mathrm{CSP}(T_1 \cup T_2)$ (unless P=NP).


    Volume: Volume 16, Issue 1
    Published on: February 20, 2020
    Accepted on: January 7, 2020
    Submitted on: May 20, 2019
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,03C98, 03D15, 08A70,F.4.1,F.2.2,G.2.1
    Funding:
      Source : OpenAIRE Graph
    • Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones; Funder: European Commission; Code: 681988

    1 Document citing this article

    Consultation statistics

    This page has been seen 1085 times.
    This article's PDF has been downloaded 286 times.