Towards a finer classification of the complexity of constraint satisfaction problems

对约束满足问题的复杂性进行更精细的分类

• 批准号: 312397-2008
• 负责人: Tesson, Pascal
• 金额: $ 1.75万
• 依托单位: Université Laval
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=396807
• 关键词: Towards; finer; classification; complexity; constraint

The main objective of the proposal is the continued study of the computational complexity of constraint satisfaction problems (CSP). CSP offer a unified framework to analyze a wide variety of computational problems that occur naturally in many areas of computer science, most notably in artificial intelligence, database theory and combinatorial optimization.

本文的主要目标是继续研究约束满足问题（CSP）的计算复杂度。CSP提供了一个统一的框架来分析在计算机科学的许多领域中自然发生的各种计算问题，特别是在人工智能，数据库理论和组合优化方面。