For a first-order theory $T$, the Constraint Satisfaction Problem of $T$ is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of $T$. In this article we develop sufficient conditions for polynomial-time tractability of the constraint satisfaction problem for the union of two theories with disjoint relational signatures. To this end, we introduce the concept of sampling for theories and show that samplings can be applied to examples which are not covered by the seminal result of Nelson and Oppen.
翻译:就一阶理论$T美元而言,限制满意度问题$T是确定某种原子公式的某一组合在某种模型($T美元)中是否可加以比较的计算问题。在本条中,我们为两种理论的结合与脱节关系签名的制约满足度问题制定了充分的条件,为多时可调和的制约满足问题提供了充分的条件。为此,我们引入了理论抽样的概念,并表明抽样可以适用于Nelson和Oppen的开创性结果所不包括的例子。