Symbolic Computation and Complexity Theory

Symbolic Computation and Complexity Theory

The discipline of symbolic computation goes back to be beginnings of computers, as early on scientists carried out symbolic (exact) and algebraic manipulation of polynomials and quantified formulas on early computers.  The theory of NP-completeness has exposed many of the investigated problems hard in the worst case. As it turned out in the 1980s, an exception is the problem of polynomial factoring, that unlike the problem of integer factoring
is in random polynomial time even when representing the input polynomial by a straight-line program.

Today's highly sophisticated and finely tuned algorithms, e.g., for Groebner basis reduction and real algebraic geometry, can solve many of the mathematical problems arising in science and engineering. Symbolic and hybrid symbolic-numeric methods operate on the fine line between the doable and the hard, that also when the difference is a quadratic vs. a linear complexity but when the intermediate data is exceedingly large.

By way of examples ranging from sparse linear algebra over factorization to sparse multidimensional model synthesis, in my talk I will attempt to separate algorithmic problems that are doable from those that areprovably hard.  I will give my answer on the role of algorithms whoserunning time is exponential in input size.