An Algebraic Characterisation of Complexity for Valued Constraint
An Algebraic Characterisation of Complexity for Valued Constraint
复制标题
有价值约束复杂性的代数表征
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Jeavons
中科院分区：
文献类型：
--
作者：
D. Cohen;Martin C. Cooper;P. Jeavons
经典的约束满足是关于满足一组约束的可行性。这个框架的扩展，包括优化，现在也正在调查和所谓的软约束理论正在开发中。在这个扩展的框架中，约束允许的值的元组被赋予期望权重或成本，目标是找到最期望（或最小成本）的分配。
任何优化问题的复杂性都取决于必须最小化的函数类型。对于软约束问题，该函数是从一些固定的可用成本函数集合中选择的成本函数的总和，称为值约束语言。在本文中，我们表明，当成本是有理数或无限的软约束问题的复杂性是由一定的代数性质的值约束语言，我们称之为可行性多态性和分数多态性。
作为这些结果的直接应用，我们证明了一个非平凡的分数多态性的存在是一个有价值的约束语言在任何有限域（假设P <$NP）上的合理或无限成本的易处理性的必要条件。
Classical constraint satisfaction is concerned with the feasibility of satisfying a collection of constraints. The extension of this framework to include optimisation is now also being investigated and a theory of so-called soft constraints is being developed. In this extended framework, tuples of values allowed by constraints are given desirability weightings, or costs, and the goal is to find the most desirable (or least cost) assignment.
The complexity of any optimisation problem depends critically on the type of function which has to be minimized. For soft constraint problems this function is a sum of cost functions chosen from some fixed set of available cost functions, known as a valued constraint language. We show in this paper that when the costs are rational numbers or infinite the complexity of a soft constraint problem is determined by certain algebraic properties of the valued constraint language, which we call feasibility polymorphisms and fractional polymorphisms.
As an immediate application of these results, we show that the existence of a non-trivial fractional polymorphism is a necessary condition for the tractability of a valued constraint language with rational or infinite costs over any finite domain (assuming P ≠ NP).