非常抱歉，
你要访问的页面不存在，
非常抱歉，
你要访问的页面不存在，
非常抱歉，
你要访问的页面不存在，
验证码：
职称:Distinguished Career Professor Of CSDistinguished Career Professor Of CS
所属学校:Carnegie Mellon University
所属院系:Computer Science Department
所属专业:Computer Science
联系方式: 412-268-8139
Complexity and Real Computation. In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction: "The classical theory of computation had its origin in the work of logicians -- of Godel, Turing, ... , among others -- in the 1930's. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science. "The point of view of this book is that the Turing model (we call it "classical") with it's dependence on 0's and 1's, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms." Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z_2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question "does P= NP?" make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert's Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations. Transfer Principles for Complexity Theory. A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z_2. But now we have an additional powerful tool, namely that of transfer: When there was essentially only one model of computation (i.e. over Z_2), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P=NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z_2? (Answer: Yes and essentially yes.) I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.
Complexity and Real Computation. In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction: "The classical theory of computation had its origin in the work of logicians -- of Godel, Turing, ... , among others -- in the 1930's. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science. "The point of view of this book is that the Turing model (we call it "classical") with it's dependence on 0's and 1's, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms." Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z_2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question "does P= NP?" make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert's Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations. Transfer Principles for Complexity Theory. A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z_2. But now we have an additional powerful tool, namely that of transfer: When there was essentially only one model of computation (i.e. over Z_2), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P=NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z_2? (Answer: Yes and essentially yes.) I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.
