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 :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101925
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:53 AM
Last modification on : Friday, May 17, 2019 - 1:39:21 AM

File

RR1997-38.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101925, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

25