Decision versus Evaluation in Algebraic Complexity Theory
Presenter
April 19, 2007
Abstract
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.