Computational Complexity of Geometric and Combinatorial Problems

几何和组合问题的计算复杂性

• 批准号: RGPIN-2016-04274
• 负责人: Kirkpatrick, David
• 金额: $ 3.68万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634421
• 关键词: Computational; Complexity; Geometric; Combinatorial; Problems

The primary objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. This will be achieved by providing qualitative and quantitative answers to the questions: (i) "In what ways and to what extent do certain features (attributes of specific problem instances, or of the computational framework in which they are being addressed) contribute to the intrinsic difficulty of solving problems in a particular family?" and its complement (ii) "In what ways and to what extent can we exploit certain naturally occurring features or constraints, or modify the computational framework, to provide more efficient solutions to practical instances of these problems?"

拟议研究的主要目的是进一步了解许多基本组合和几何问题的固有计算复杂性。这将通过为问题提供定性和定量答案来实现：（i）“在什么方面和在什么方面具有某些特征（特定问题实例的属性或解决的计算框架的属性）为该问题做出了贡献）在特定家庭中解决问题的内在困难？”它的补充（ii）”“以多种方式以及在多大程度上可以利用某些天然发生的特征或约束或修改计算框架，以为这些问题的实际实例提供更有效的解决方案？”