[Colloquium] Reminder: today's talk by Lenore Blum
Margery Ishmael
marge at cs.uchicago.edu
Mon May 12 10:01:41 CDT 2003
------------------------------------------------------------------------
DEPARTMENT OF COMPUTER SCIENCE
& TOYOTA TECHNOLOGICAL INSTITUTE
Monday, May 12, 2003 at 2:30 pm in Ryerson 251
------------------------------------------------------------------------
Speaker: Lenore Blum
From: Carnegie Mellon University
Title: "Computing over the Reals: Where Turing Meets Newton"
Abstract:
The classical (Turing) theory of computation has been extraordinarily
successful in providing the foundations and framework for theoretical
computer science. Yet it's dependence on 0's and 1's is fundamentally
inadequate for providing such a foundation for modern scientific
computation where most algorithms --with origins in Newton, Euler, Gauss,
et al.-- are real number algorithms.
In 1989, Mike Shub, Steve Smale and I introduced a theory of computation
and complexity over an arbitrary ring or field R. If R is Z_2 = {0,1}, the
classical computer science theory is recovered. If R is the field of real
numbers, Newton's algorithm, the paradigm algorithm of numerical analysis,
fits naturally into our model of computation.
Complexity classes P, NP and the fundamental question ?Does P= NP?? can be
formulated naturally over an arbitrary ring R. The answer to the
fundamental question depends on the complexity of deciding feasibility of
polynomial systems over R. When R is Z_2, this becomes the classical
satisfiability problem of Cook-Karp-Levin. When R is the field of complex
numbers, the answer depends on the complexity of Hilbert's Nullstellensatz.
The notion of reduction between discrete problems (e.g. between traveling
salesman and satisfiability) has been a powerful tool in classical
complexity theory. But now, in addition, the transfer of complexity results
between domains (discrete and continuous) becomes a real possibility.
In this talk, I will discuss these results and indicate how basic notions
from numerical analysis such as condition, round off and approximation are
being introduced into complexity theory, bringing together ideas
germinating from the real calculus of Newton and the discrete computation
of computer science. Speaker's homepage: http://www-2.cs.cmu.edu/~lblum/
*The talk will be followed by refreshments in Ryerson 255*
Hosts: Stephen Smale & Partha Niyogi
More information about the Colloquium
mailing list