Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domaines permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l'analyse d'algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d'algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00677977 |
| Date | 29 November 2011 |
| Creators | Briquel, Irénée |
| Publisher | Ecole normale supérieure de lyon - ENS LYON |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0024 seconds