# 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

hard.

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

hard.