Complexité structurelle et complexité de requête pour des problèmes totaux
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
In this thesis, we treat problems of structural complexity, which aims at classifying problems depending on their relative difficulty to be solved, and we also study the existence of an efficient solution to a more concrete problem of online algorithmics. Following this dichotomy, in the first part of this thesis we study some problems of the class TFNP, more specifically Sperner problems and the search for a local minimum. We prove completeness of locally 2-dimensional Sperner problems in the ``Parity Argument'' classes PPA, PPAD and PPADS. Thus, we improve results of Papadimitriou and Grigni. We also study the number of queries, both in the classical and the quantum settings, necessary to solve an arbitrary dimensional Sperner problem on a pseudo-manifold ; we prove a lower bound and an upper bound corresponding to the complexity of an algorithm, the latter being optimal for a particular case previously studied by Crescenzi and Grigni. Finally, we give a classical and a quantum algorithm for spotting a local minimum of a function defined over the vertices of a graph, and prove that they use fewer queries than previously known algorithms on large classes of graphs. The analyses of our two algorithms rely on the use of {\em separator theorems}, and we prove such a theorem which slightly improves an older result of Gilbert, Hutchinson and Tarjan. In the second part of this thesis, we study the existence of a memoryless online algorithm for the CNN problem. Our results generalize and improve a previous result of Koutsoupias and Taylor.
Abstract FR:
Dans cette thèse, nous abordons des problèmes de complexité structurelle, traitant de la classification des problèmes en fonction de leurs difficultés relatives, et nous nous intéressons aussi à l'existence d'une solution à un problème plus concret d'algorithmique en-ligne. Suivant cette dichotomie, dans la première partie de cette thèse nous étudions des problèmes de la classe des problèmes totaux TFNP, à savoir les problèmes de Sperner et la recherche de minimum local. Nous montrons les complétudes de problèmes de Sperner localement 2-dimensionnels dans les classes d'arguments de parité PPA, PPAD et PPADS. Nous améliorons ainsi des résultats de Papadimitriou et Grigni. Nous étudions ensuite le nombre de requêtes, au sens classique et au sens quantique, nécessaires pour résoudre un problème de Sperner en dimension arbitraire sur une pseudo-variété ; nous prouvons une borne inférieure ainsi qu'une borne supérieure correspondant à la complexité d'un algorithme, cette dernière étant optimale pour un cas précédemment étudié par Crescenzi et Silvestri. Enfin, nous donnons deux algorithmes, un classique et un quantique, pour déterminer la position d'un minimum local d'une fonction définie sur les sommets d'un graphe. Les analyses de nos deux algorithmes sont fondées sur l'existence de séparateurs de petite taille dans les graphes, et nous montrons un tel résultat qui améliore un résultat antérieur de Gilbert, Hutchinson et Tarjan. Dans la seconde partie de la thèse, nous nous intéressons à l'existence d'un algorithme en-ligne sans mémoire pour le problème CNN. Notre résultat généralise et améliore un résultat antérieur de Koutsoupias et Taylor.