一句话：证明两个时间结构理论的 CSP 并集要么多项式时间可解，要么 NP 完全。
论文研究两个签名不相交的时间理论 T1 与 T2 的并 T1∪T2 的约束满足问题 CSP(T1∪T2) 的计算复杂度。时间结构指所有关系均可在一阶逻辑中由 (Q;<) 定义的结构。作者证明：若 T1、T2 均为时间结构理论，则 CSP(T1∪T2) 要么在 P 中，要么是 NP 完全的。证明核心是一个纯代数结论：刻画了 Q 上包含 Aut(Q;<) 的局部闭克隆格的结构，从而排除中间复杂度。该结果为时间结构理论的组合 CSP 给出了 P 与 NP 完全之间的二分性。
The constraint satisfaction problem (CSP) of a first-order theory T is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of T. We study the computational complexity of CSP$(T_1 \cup T_2)$ where $T_1$ and $T_2$ are theories with disjoint finite relational signatures. We prove that if $T_1$ and $T_2$ are the theories of temporal structures, i.e., structures where all relations have a first-order definition in $(Q;<)$, then CSP$(T_1 \cup T_2)$ is in P or NP-complete. To this end we prove a purely algebraic statement about the structure of the lattice of locally closed clones over the domain $Q$ that contain Aut$(Q;<)$.
@article{paperbot1700,
title = {Tractable Combinations of Temporal CSPs},
author = {Manuel Bodirsky and Johannes Greiner and Jakub Rydval},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 2},
year = {2022},
doi = {10.46298/lmcs-18(2:11)2022}
}