Are lower bounds easier over the reals ? - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Are lower bounds easier over the reals ?

Résumé

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.
Fichier principal
Vignette du fichier
RR1997-38.pdf (248.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101925 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101925 , version 1

Citer

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⟩
9 Consultations
117 Téléchargements

Partager

Gmail Facebook X LinkedIn More