SMF

Sur la complexité du principe de Tarski-Seidenberg

Joos Heintz, Marie-Françoise Roy, Pablo Solernó
Sur la complexité du principe de Tarski-Seidenberg
  • Consulter un extrait
  • Année : 1990
  • Fascicule : 1
  • Tome : 118
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Pages : 101-126
  • DOI : 10.24033/bsmf.2138
Cet article est consacré à un algorithme d'élimination des quantificateurs dans les corps réels clos dont la complexité est simplement exponentielle en séquentiel (et polynomiale en parallèle) en le nombre de variables dès lors que le nombre d'alternances de quantificateurs est fixé.
This paper is devoted to an algorithm for quantifier elimination in the real closed case which is of complexity single exponential in the number of variables in the sequential model (and polynomial in the parallel model) as soon as the number of alternations of quantifiers is fixed.