Algebraic Methods for Quantified Constraints

量化约束的代数方法

• 批准号: EP/X03190X/1
• 负责人: Barnaby Martin
• 金额: $ 66.36万
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX03190X%2F1
• 关键词: Algebraic; Methods; Quantified; Constraints

The constraint satisfaction problem (CSP) is a paradigm in which it is possible to express, in a natural way, a wide range of problems arising in many areas of Computer Science and beyond, e.g. Artificial Intelligence, Computational Linguistics, Computational Biology, Combinatorics and Databases. A CSP instance involves a finite set of variables, a set of values (the domain) and a finite set of constraints. The task is to assign the variables to the values so as to satisfy all of the constraints. The CSP can be seen as a model-checking problem for the fragment of first-order logic that has just existential quantification, conjunction and equality. When universal quantification is added, the new paradigm is the quantified constraint satisfaction problem (QCSP). When the problem is parameterised by the language of constraints permitted, one finds for some types of constraint, the task of finding a solution is computationally easy (i.e. requires a feasible amount of computational resources such as running time and memory), but for many types, it is computationally hard. The complexity classification across finite constraint languages for the CSP was completed in 2017, independently by Bulatov and Zhuk, and is now known to be a dichotomy between polynomial time and NP-complete. The similar classification problem for the QCSP represents the only connective-based syntactic fragment of first-order logic where the outcome is not known. Recently, Zhuk and Martin (2019) refuted the Chen Conjecture that only complexities of polynomial time, NP-complete and Pspace-complete would in this classification. It is now known that exotic complexity classes such as DP-complete, Theta^P_2-complete and Pi^P_2-complete can be realised in QCSPs. Zhuk and Martin (2019) completed the three-element domain classification as a tetrachotomy between polynomial time, NP-complete, co-NP-complete and Pspace-complete. This proposal aims to take Zhuk's new methods beyond the three-element case to larger domains. The proposal will consider all finite domains, as well as some infinite domains where the constraint languages model notions from temporal reasoning. The central objective of the proposal is to map out landscapes of computational complexity across these constraint languages.

约束满足问题（CSP）是一种范式，可以以自然的方式表达计算机科学及其他领域中出现的各种问题，例如计算机科学。人工智能、计算语言学、计算生物学、组合学和数据库。 CSP 实例涉及一组有限的变量、一组值（域）和一组有限的约束。任务是将变量分配给值以满足所有约束。 CSP 可以看作是仅具有存在量化、合取和等式的一阶逻辑片段的模型检查问题。当添加通用量化时，新的范式是量化约束满足问题（QCSP）。当问题通过允许的约束语言参数化时，我们发现对于某些类型的约束，找到解决方案的任务在计算上很容易（即需要可行的计算资源量，例如运行时间和内存），但对于许多类型，这在计算上是困难的。 CSP 的跨有限约束语言的复杂性分类于 2017 年由 Bulatov 和 Zhuk 独立完成，现在已知是多项式时间和 NP 完全之间的二分法。 QCSP 的类似分类问题代表了一阶逻辑中唯一基于连接词的句法片段，其中结果未知。最近，Zhuk 和 Martin（2019）反驳了陈猜想，即只有多项式时间、NP 完全和 P 空间完全的复杂性才属于这种分类。现在已知，诸如 DP-complete、Theta^P_2-complete 和 Pi^P_2-complete 等奇异复杂性类别可以在 QCSP 中实现。 Zhuk 和 Martin (2019) 以多项式时间、NP 完全、共 NP 完全和 P 空间完全之间的四分法完成了三元素域分类。该提案旨在将 Zhuk 的新方法从三元素案例扩展到更大的领域。该提案将考虑所有有限域以及一些无限域，其中约束语言对时间推理的概念进行建模。该提案的中心目标是绘制出这些约束语言的计算复杂性图景。