|
NeuroCOLT
Technical Report NC-TR-98-004
Are
Lower Bounds Easier over the Reals?
Herve Fournier and Pascal Koiran
ENS Lyon
Keywords:Algebraic
complexity, real Turing machine
Received:
04-MAR-1998
Abstract
We show that proving lower bounds in algebraic models of computation
may not be easier than in the standard Turing machine model. For instance,
a superpolynomial lower bound on the size of an algebraic circuit
solving the real knapsack problem (or on the running time of a real
Turing machine) would imply a separation of P from PSPACE. A more
general result relates parallel complexity classes in boolean and
real models of computation. We also propose a few problems in algebraic
complexity and topological complexity.
Download Compressed Postscript
|