Computational Complexity of Continuous Problems

摘要

Computational complexity studies the intrinsic difficulty of solving mathematically posed problems. Discrete computational com-plexity studies discrete problems and often uses the Turing machine model of computation. Continuous computational complexity studies continuous problems and tends to use the real number model. Continuous computational complexity may be split into two branches. The first deals with problems for which, the information is complete. Informally, information may be complete for problems which are specified by a finite number of inputs. Examples include matrix multiplication, solving linear systems or systems of polynomial equations. We mention two specific results. The first is for matrix multiplication of two real n x n matrices. The trivial lower bound on the complexity is of order n2, whereas the best known upper bound is of order n2'378 as proven by D. Coppersmith and S. Winograd. The actual complexity of matrix multiplication is still unknown. The second result is for the problem of deciding whether a system of n real polynomials of degree 4 has a real root. This problem is NP-complete over the reals as proven by L. Blum, M. Snub and S. Smale.