Complexity of Combinations of Qualitative Constraint Satisfaction Problems
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
The CSP of a first-order theory T is the problem of deciding for a given finite set S of atomic formulas whether (Formula Presented) is satisfiable. Let T1 and T2 be two theories with countably infinite models and disjoint signatures. Nelson and Oppen presented conditions that imply decidability (or polynomial-time decidability) of (Formula Presented) under the assumption that CSP(T1) and CSP(T2 are decidable (or polynomial-time decidable). We show that for a large class of ω-categorical theories T1, T2 the Nelson-Oppen conditions are not only sufficient, but also necessary for polynomial-time tractability of (Formula Presented) (unless P = NP).
Details
| Original language | English |
|---|---|
| Title of host publication | Automated Reasoning - 9th International Joint Conference, IJCAR 2018, Held as Part of the Federated Logic Conference, FloC 2018, Proceedings |
| Editors | Roberto Sebastiani, Didier Galmiche, Stephan Schulz |
| Publisher | Springer, Berlin [u. a.] |
| Pages | 263-278 |
| Number of pages | 16 |
| ISBN (print) | 9783319942049 |
| Publication status | Published - 2018 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Computer Science, Volume 10900 |
|---|---|
| ISSN | 0302-9743 |
Conference
| Title | 9th International Joint Conference on Automated Reasoning, IJCAR 2018 Held as Part of the Federated Logic Conference, FloC 2018 |
|---|---|
| Duration | 14 - 17 July 2018 |
| City | Oxford |
| Country | United Kingdom |
External IDs
| ORCID | /0000-0001-8228-3611/work/142241086 |
|---|