Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
基本信息
- 批准号:RGPIN-2017-05107
- 负责人:
- 金额:$ 1.46万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2018
- 资助国家:加拿大
- 起止时间:2018-01-01 至 2019-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In a constraint satisfaction problem (CSP), one must assign values to variables that must satisfy various constraints; typical real world examples include scheduling problems, database queries, image-processing, and frequency assignment problems. In general, determining whether a CSP admits a solution is an algorithmic challenge, but it often happens in practice that the constraints are of a very restricted form, allowing the use of efficient methods to solve the CSP. Our long-term goal is to classify precisely what kinds of restrictions lead to these tractable CSP's. Our approach is based on an unexpected and fruitful connection between CSP's and universal algebra that was uncovered in the late 90's, and which has led to major breakthroughs in our understanding of the complexity of CSPs over the past 20 years. In short, every family of constraints is transformed into a mathematical object whose algebraic properties reflect the difficulty of solving the CSP. Several precise conjectures have been formulated, predicting which equations should lead***to solvability with given time and space restrictions. The goal of this program is to investigate and solve these conjectures in various important special cases. The investigation of special cases of the refined dichotomy conjectures is bound to provide insights into an eventual solution of the full L- and NL- conjectures. This will give us a complete classification of the complexity of CSPs of bounded width, and hence a much deeper understanding of the complexity of non-uniform CSPs, which are ubiquitous in the theory of computing, with wide-ranging applications from artificial intelligence to database theory.
在约束满足问题(CSP)中,一个人必须为必须满足各种约束的变量赋值;典型的现实世界例子包括调度问题、数据库查询、图像处理和频率分配问题。一般来说,确定CSP是否接受解决方案是一个算法挑战,但在实践中经常发生的情况是,约束的形式非常有限,允许使用有效的方法来求解CSP。我们的长期目标是准确地分类导致这些易处理的CSP的是哪种限制。我们的方法是基于90年代末S发现的CSP和泛代数之间的一种意想不到且卓有成效的联系,这使得我们在过去20年里对CSP的复杂性的理解取得了重大突破。简而言之,每一族约束都被转化为一个数学对象,其代数性质反映了求解CSP的难度。已经提出了几个精确的猜想,预测在给定的时间和空间限制下,哪些方程*应该是可解的。这个项目的目标是调查和解决各种重要特殊情况下的这些猜想。对精化二分猜想特例的研究,必将为L猜想和NL猜想的最终解决提供新的思路。这将使我们对有限宽度CSP的复杂性有一个完整的分类,从而对非均匀CSP的复杂性有更深刻的理解,非均匀CSP在计算理论中普遍存在,从人工智能到数据库理论都有广泛的应用。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Larose, Benoit其他文献
Larose, Benoit的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Larose, Benoit', 18)}}的其他基金
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2021
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2020
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2019
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Promise Constraint Satisfaction Problem: Structure and Complexity
承诺约束满足问题:结构和复杂性
- 批准号:
EP/X033201/1 - 财政年份:2024
- 资助金额:
$ 1.46万 - 项目类别:
Fellowship
AF: Small: Streaming Complexity of Constraint Satisfaction Problems
AF:小:约束满足问题的流复杂性
- 批准号:
2152413 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Standard Grant
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2021
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2020
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
The complexity of the constraint satisfaction problem and its variants
约束满足问题及其变体的复杂性
- 批准号:
RGPIN-2015-04656 - 财政年份:2019
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2019
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
The Complexity of Promise Constraint Satisfaction
承诺约束满足的复杂性
- 批准号:
EP/R034516/1 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Research Grant
The complexity of the constraint satisfaction problem and its variants
约束满足问题及其变体的复杂性
- 批准号:
RGPIN-2015-04656 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Refined complexity of constraint satisfaction problems
约束满足问题的精细化复杂性
- 批准号:
RGPIN-2017-05107 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
The complexity of the constraint satisfaction problem and its variants
约束满足问题及其变体的复杂性
- 批准号:
RGPIN-2015-04656 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual