Skip to Main content Skip to Navigation

Are lower bounds easier over the reals ?

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.
Document type :
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:53 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 AM


Files produced by the author(s)


  • HAL Id : hal-02101925, version 1



Pascal Koiran, Hervé Fournier. Are lower bounds easier over the reals ?. [Research Report] LIP RR-1997-38, Laboratoire de l'informatique du parallélisme. 1997, 2+13p. ⟨hal-02101925⟩



Les métriques sont temporairement indisponibles