Complexity of algorithms in low-dimensional topology

这个建议涉及三维空间表面研究的计算方面。结识别问题是此类问题的一个关键例子，它寻求一种方法来确定三维空间中的两条曲线何时可以相互变形。它的计算复杂性，即运行这种算法所需的步骤数，仍然没有完全被理解。对这个问题的研究揭示了复杂性理论、低维拓扑、跨越曲线的曲面需要多大面积的问题（微分几何中的一个问题）和关于如何用尽可能少的三角形构造曲面的问题（计算几何的一部分）之间有趣和意想不到的联系。研究者计划证明这个问题，已经被称为NP问题的一类，也属于coNP问题的一类。他进一步致力于改进已知的运行时间和相关问题的上界和下界，并探索与计算几何和微分几何的联系。三维流形和其中包含的表面模拟了我们生活的世界中的物体。他们的数学理论既自然又广泛适用。计算问题在这些领域的研究中发挥着越来越大的作用。计算复杂性是理论计算机科学的一个领域，研究算法及其运行时间。许多重要的算法都有几何成分，而几何方法可以使我们深入了解高效的计算。源自拓扑学和几何学的技术已经导致了计算机图形学、可视化、医学和分子建模以及图像识别方面算法的改进。本建议所考虑的问题涉及分析几何物体性质的算法的构建，以及这些算法的计算复杂性的分析。

This proposal concerns computational aspects of the study of surfaces in three dimensional space. The Knot Recognition Problem, a key example of such problems, seeks a procedure to determine when two curves in 3-space can be deformed to one another. Its computational complexity, the number of steps required to run such an algorithm, is still not completely understood. Investigations into this problem have revealed intriguing and unexpected connections between complexity theory, low-dimensional topology, the question of how much area is required of a surface spanning a curve (a problem in differential geometry), and questions concerning how to construct surfaces with as few triangles as possible (part of computational geometry). The investigator plans to show that this problem, already known to be in a class of problems called NP, is also in a class called coNP. He further aims to improve both upper and lower bounds on the running times known for this and related problems, and to explore connections to computational and differential geometry.Three dimensional manifolds and the surfaces contained in them model objects that are found in the world we live in. Their mathematical theory is both natural and widely applicable. Computational issues are playing an increasing role in investigations in these areas. Computational complexity, a field in theoretical computer science, studies algorithms and their running times. Many important algorithms have geometric components, and geometric methods can lead to insights into efficient computation. Techniques originating in topology and geometry have led to improved algorithms in computer graphics, visualization, medical and molecular modeling and image recognition. The problems considered in this proposal concern the construction of algorithms to analyze the nature of geometrical objects, and the analysis of the computational complexity of these algorithms.