Videos

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.