Are lower bounds easier over the reals?
Hervé Fournier, Pascal Koiran · 1998
We show that proving lower bounds in algebraic models of computntion may not be easier than in the standard %ring 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 'Brring 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,