Complexity of partition problems

分区问题的复杂性

• 批准号: 5075-2009
• 负责人: Hell, Pavol
• 金额: $ 4.37万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=520766
• 关键词: Complexity; partition; problems

Constraint satisfaction problems model many problems in scheduling, logistics, databases, and artificial intelligence. It has been observed that when the constraint language (or the constraint 'template') is fixed, the problems seem to fall into only two categories - polynomial time solvable or NP-complete. On the other hand, it is known that (unless P=NP) there must exist problems which are not solvable in polynomial time, but which are not quite NP-complete. Whether or not there are such 'intermediate' constraint satisfaction problems (with a fixed template) has become a very important open problem in theoretical computer science, driving much research effort based on algebra, analysis, logic, and combinatorics. Graphs seem to have an important role to play. Our results in graph theory have motivated the original problem, as well as several subsequent developments. It now appears that they will continue to motivate the research efforts. In this proposal, we propose research in the complexity of certain variants of graph homomorphism problems which would have implications for (variants of) general constraint satisfaction problems. These include list homomorphism, minimum cost homomorphism, and matrix partition problems.

约束满足问题模拟了调度、物流、数据库和人工智能中的许多问题。已经观察到，当约束语言（或约束“模板”）固定时，问题似乎只分为两类-多项式时间可解或NP完全。另一方面，已知（除非P=NP）一定存在在多项式时间内不可解的问题，但这些问题不是NP完全的。是否存在这样的“中间”约束满足问题（具有固定模板）已经成为理论计算机科学中一个非常重要的开放问题，推动了基于代数，分析，逻辑和组合学的许多研究工作。图表似乎扮演着重要的角色。我们在图论中的结果激发了最初的问题，以及随后的几个发展。现在看来，他们将继续推动研究工作。在这项建议中，我们提出了研究的复杂性，某些变种的图同态问题，这将有影响（变种）一般的约束满足问题。这些问题包括列表同态、最小代价同态和矩阵划分问题。