Decision versus Evaluation in Algebraic Complexity Theory

Thursday, April 19, 2007 - 10:30am - 11:20am
EE/CS 3-180
Pascal Koiran (École Normale Supérieure de Lyon)
wo main categories of problems are studied in algebraic complexity theory:
evaluation problems and decision problems. A typical example of an evaluation
problem is the evaluation of the permanent of a matrix. Such problems can be
studied within Valiant's framework.

Deciding whether a multivariate polynomial has a real root is a typical example
of a decision problem. This problem is NP-complete in the Blum-Shub-Smale model
of computation over the real numbers.

In this talk I will present a transfer theorem which shows that if certain
evaluation problems are easy, then other decision problems (including the
above-mentioned NP-complete problem) are easy too.

Therefore, to show that that P is different from NP over the set of real
numbers, one should first be able show that certain evaluation problems are