We study the constraint satisfaction problem (CSP) parameterized by a constraint language Γ (CSP(Γ)) and how the choice of Γ affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSP(Γ) problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S_D such that the time complexity of the NP-complete problem CSP({S_D}) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({S_D}) strictly decreases when |D| increases (unless the ETH is false) and provide stronger complexity results in the special case when |D| = 3.
展开▼
机译：我们研究由约束语言γ（CSP（γ））参数化的约束满足问题（CSP），以及如何选择γ的最坏情况时间复杂度。在指数 - 时的假设（ETH）下，我们排除了有限域NP完整CSP（γ）问题的子折叠算法的存在。这延伸到某些无限域CSP和结构上限制的问题。对于具有有限域D的CSP以及所有联合关系可用，我们识别一个关系S_D，使得NP完整问题CSP（{S_D}）的时间复杂度是所有NP完整的CSP的下限。我们还证明了CSP（{S_D}）的时间复杂性严格地减少| D |增加（除非Eth是假）并在特殊情况下提供更强的复杂性结果| D | D | = 3。
展开▼
