Computational Complexity of Geometric and Combinatorial Problems

提出的研究的主要目的是进一步我们对一些基本组合和几何问题的固有计算复杂性的理解。这将通过对下列问题提供定性和定量的回答来实现：(i)“某些特征（特定问题实例的属性，或正在处理这些问题的计算框架的属性）以何种方式和在何种程度上有助于解决特定家庭问题的内在困难？”及其补充（ii）“我们可以以何种方式和在何种程度上利用某些自然发生的特征或约束，或修改计算框架，为这些问题的实际实例提供更有效的解决方案？”

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?"