Robustly Tractable Constraint Satisfaction Problems

鲁棒可处理的约束满足问题

基本信息

批准号：
EP/J000078/1
负责人：
Andrei Krokhin
金额：
$ 10.01万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2012
资助国家：
英国
起止时间：
2012 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FJ000078%2F1
关键词：
Robustly Tractable Constraint Satisfaction Problems

项目摘要

The constraint satisfaction problem, or CSP for short, provides a general framework in which it is possible to express, in a natural way, a wide variety of problems from artificial intelligence and computer science. The basic aim in a constraint satisfaction problem is to decide whether there is an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables (decision version, CSP), or to find an assignment satisfying a maximum number of constraints (optimisation version, Max CSP). Nowadays, the CSP is extensively used in theoretical computer science, being a mathematical object with very rich structure that provides an excellent laboratory both for classification methods and for algorithmic techniques. One particular family of CSPs that receives a great amount of attention in complexity theory are the CSPs with a fixed constraint language, i.e. with a restriction on the types of constraints.A polynomial-time algorithm for a CSP, in general, only needs to tell satisfiable instances from unsatisfiable, i.e. it treats all unsatisfiable instances the same. When can such an algorithm be made to also identify near-misses, i.e. almost satisfiable instances - those where a tiny fraction of constraints can be removed to make the instance satisfiable? We call this type of tractability robust. We plan to develop a new research programme investigating a notion of tractability for CSP with a fixed constraint language that combines in a natural way two very advanced (both technically and conceptually), but so far practically disjoint, directions in the theory of computation: studying classical tractability and approximability of constraint satisfaction problems via algebraic/logical and analytic methods, respectively.

约束满意度问题（或简称CSP）提供了一个一般框架，在该框架中，可以自然地表达来自人工智能和计算机科学的各种问题。约束满意度问题的基本目的是确定是否有一个给定变量集值分配值，但要受到可以同时分配给某些变量（决策版本，CSP）的指定子集的值的约束，还是找到满足最大约束数量（优化版本，最大CSP）的分配。如今，CSP广泛用于理论计算机科学，是一个具有非常丰富的结构的数学对象，为分类方法和算法技术提供了出色的实验室。在复杂性理论中受到大量关注的CSP家族是具有固定约束语言的CSP，即对约束类型的限制。一种CSP的多项式时间算法，通常只需要从无法满足的情况下告诉可满足的实例，即它处理所有不适合的实例。什么时候可以制定这种算法以确定几乎令人满意的实例 - 可以删除一小部分约束以使实例令人满意的情况？我们称这种类型的易处理性可靠。我们计划开发一项新的研究计划，研究CSP的障碍概念，其固定的约束语言以一种自然的方式结合了两个非常先进的（在技术上和概念上），但到目前为止，实际上在计算理论中的方向是不相关的：研究经典障碍性和通过代数/逻辑/逻辑/逻辑和分析方法的约束满意度问题的近似性。