Are lower bounds easier over the reals ?

Pascal Koiran (1) , Hervé Fournier (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

On montre qu'il n'est pas toujours plus facile d'obtenir des bornes inférieures dans des modèles de calcul algébriques que dans le modèle classique de la machine de Turing. Par exemple, une borne inférieure superpolynomiale sur la taille d'un circuit algébrique résolvant le problème du sac-à-dos réel (ou sur le temps de calcul d'une machine de Turing réelle) impliquerait une séparation de P et PSPACE. Un résultat plus général établit des relations entre classes de complexité parallèles dans les modèles de calcul booléens et réels. On propose aussi quelques problèmes de complexité algébriques et de complexité topologique.

Mots clés: Algebraic Complexity; Decision Trees; Lower Bounds; Range Searching

Mots clés: Arbres de Décision; Bornes Inférieures; Complexité Algébrique; Localisation de Points

Domaines: Informatique [cs]

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⟩