In 1988 Blum joined the Theory Group of the newly formed International Computer Science Institute (ICSI) in Berkeley. She spent part of the next two years in New York as Visiting Professor at the CUNY Graduate Center and returned to New York in 1987 as Visiting Scientist at the IBM T.J. An NSF Career Advancement Award in 1983 enabled Blum to embark on a longtime scientific collaboration with Mike Shub. In 1979 she was awarded the first Letts-Villard Chair at Mills.
In 1973 she joined the faculty of Mills College where in 1974 she founded the Mathematics and Computer Science Department (serving as its Head or co-Head for 13 years). She then went to the University of California at Berkeley as a Postdoctoral Fellow and Lecturer in Mathematics. in mathematics from the Massachusetts Institute of Technology in 1968 (the same year Princeton University first allowed women to enter their graduate program). Brief Biography Lenore Blum received her Ph.D. 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.) 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. For example, we can ask: Suppose we can show P = NP over the complex numbers (using all the mathematics that is natural here). But now, in addition, the transfer of complexity results from one domain to another becomes a real possibility. between traveling salesman and satisfiability ) has been a powerful tool in classical complexity theory. The notion of reduction between problems (e.g. When R is the field of complex numbers, the answer depends on the complexity of Hilbert’s Nullstellensatz. When R is Z 2, this becomes the classical satisfiability problem of Cook-Karp-Levin. The answer to the fundamental question depends on the complexity of deciding feasibility of polynomial systems over R.
Complexity classes P, NP and the fundamental question “Does P= NP?” can be formulated naturally over an arbitrary ring R. If R is the field of real numbers, Newton’s algorithm, the paradigm algorithm of numerical analysis, fits naturally into our model of computation.
If R is Z 2 =, the classical computer science theory is recovered. In 1989, Mike Shub, Steve Smale and I introduced a theory of computation and complexity over an arbitrary ring or field R. Yet its 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. The classical (Turing) theory of computation has been extraordinarily successful in providing the foundations and framework for theoretical computer science.
0 kommentar(er)
