La complexité arithmétique est l’étude des ressources nécessaires pour calcu- ler des polynômes en n’utilisant que des opérations arithmétiques. À la fin des années 70, Valiant a défini (de manière semblable à la complexité booléenne) des classes de polynômes. Les polynômes, ayant des circuits de taille polyno- miale, considérés faciles forment la classe VP. Les sommes exponentielles de ces derniers correpondent alors à la classe VNP. L’hypothèse de Valiant est la conjecture que VP ̸= VNP.Bien que cette conjecture soit encore grandement ouverture, cette dernière semble toutefois plus accessible que son homologue booléen. La structure algé- brique sous-jacente limite les possibilités de calculs. En particulier, un résultat important du domaine assure que les polynômes faciles peuvent aussi être cal- culés efficacement en paralèlle. De plus, quitte à autoriser une augmentation raisonnable de la taille, il est possible de les calculer avec une profondeur de calcul bornée par une constante. Comme ce dernier modèle est très restreint, de nombreuses bornes inférieures sont connues. Nous nous intéresserons en premier temps à ces résultats sur les circuits de profondeur constante.Bürgisser a montré qu’une conjecture (la τ-conjecture) qui borne supérieu- rement le nombre de racines de certains polynômes univariés, impliquait des bornes inférieures en complexité arithmétique. Mais, que se passe-t-il alors, si on essaye de réduire, comme précédemment, la profondeur du polynôme consi- déré? Borner le nombre de racines réelles de certaines familles de polynômes permetterait de séparer VP et VNP. Nous étudierons finalement ces bornes su- périeures sur le nombre de racines réelles. / Arithmetic complexity is the study of the required ressources for computing poynomials using only arithmetic operations. In the last of the 70s, Valiant defined (similarly to the boolean complexity) some classes of polynomials. The polynomials which have polynomial size circuits form the class VP. Exponential sums of these polynomials correspond to the class VNP. Valiant’s hypothesis is the conjecture that VP is different tVNP.Although this conjecture is still open, it seems more accessible than its boolean counterpart. The induced algebraic structure limits the possibilities of the computation. In particular, an important result states that the low de- gree polynomials can be efficiently computed in parallel. Moreover, if we allow a fair increasement of the size, it is possible to compute them with a constant depth. As this last model is very particular, some lower bounds are known.Bürgisser showed that a conjecture (τ-conjecture) which bounds the number of roots of some univariate polynomials, implies lower bounds in arithmetic complexity. But, what happens if we try to reduce as before the depth of the circuits for the polynomials? Bounding the number of real roots of some families of polynomials would imply a separation between VP and VNP. Finally we willstudy these upper bounds on the number of real roots.
| Identifer | oai:union.ndltd.org:theses.fr/2014ENSL0921 |
| Date | 09 July 2014 |
| Creators | Tavenas, Sébastien |
| Contributors | Lyon, École normale supérieure, Koiran, Pascal |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text, StillImage |
Page generated in 0.0021 seconds