演讲人： Ker-I Ko State University of New York at Stony Brook
时间： 2004-12-23 14:30-2004-12-23 15:30
地点：FIT-1-315
内容：

This talk consists of two parts. In the first part, we present an overview of the complexity theory of real-valued functions, which studies the computational complexity of continuous functions in the context of discrete complexity theory. This theory follows the approach of recursive analysis, and uses oracle Turing machines as a basic computational model. Its main feature is to allow us to apply the discrete NP-completeness theory to analyze the computational complexity of numerical problems. In the second half of the talk, we present, within this theory, several different notions of polynomial-time computable sets in the two-dimensional plane. Since these sets are represented by real-valued functions, which are more general than the polygon representation used in computational geometry, the complexity of the associated problems becomes much higher. We demonstrate this phenomenon by the shortest path problem: While the shortest path problem in computational geometry is typically solvable in polynomial time, the problem of finding a shortest path in a polynomial-time computable two-dimensional domain is as hard as a discrete PSPACE-complete problem.
 

个人简介: