Computational Complexity of Geometric and Combinatorial Problems

建议的研究的主要目标是进一步了解一些基本的组合和几何问题的固有的计算复杂性。这将通过对以下问题提供定性和定量的答案来实现：（一）“某些特征（具体问题实例的属性，或解决这些问题的计算框架的属性）以何种方式和在何种程度上导致解决特定家庭问题的内在困难？“及其补充（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?"