The Complexity of Combinations of Qualitative Constraint Satisfaction Problems

Authors Manuel Bodirsky, Johannes Greiner

Publication date 18 January 2018

Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07) Analysis of algorithms and problem complexity (68Q25)

arXiv classification

cs.CC cs.LO math.LO

Abstract: The CSP of a first-order theory

T

is the problem of deciding for a given finite set

S

of atomic formulas whether

T c u p 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

m a t h r m C S P (T_{1} c u p T_{2})

under the assumption that

m a t h r m C S P (T_{1})

and

m a t h r m C S P (T_{2})

are decidable (or polynomial-time decidable). We show that for a large class of

o m e g a

-categorical theories

T_{1}, T_{2}

the Nelson-Oppen conditions are not only sufficient, but also necessary for polynomial-time tractability of

m a t h r m C S P (T_{1} c u p T_{2})

(unless P=NP).

This page was built for publication: The Complexity of Combinations of Qualitative Constraint Satisfaction Problems

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