论文标题
语义宽度和约束满意度问题的固定参数障碍
Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
论文作者
论文摘要
约束满意度问题（CSP）是统一处理各种突出的AI任务（例如着色或调度问题）的重要正式框架。通常，当通过约束范围参数化时，已知解决CSP是NP完整的和固定参数棘手的。我们给出了这些类别的CSP的表征，该类别的问题成为固定参数可拖延的特征。 我们的表征可大大提高CSP框架的效用，从而通过其CSP公式来确定问题的固定参数障碍。 我们进一步将表征扩展到对连接查询工会的评估，这是数据库中的一个基本问题。此外，我们还提供了有关CSP的PTIME溶解性边界的一些新见解。 特别是，我们观察到，仅对于表现出某种类型的指数生长的类，有界的分数宽度宽度比有界的Hyprete宽度更一般。 提出的工作解决了一个长期的开放问题，并在AI和数据库理论中产生了有力的新工具，以进行复杂性研究。
Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory.
