Complexity of algorithms in low-dimensional topology

点击翻译按钮获取中文摘要

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.