other · OpenGrey (Institut de l'Information Scientifique et Technique) · 2005
Structural complexity and query complexity for total problems
VERHOEVEN, Yves, SANTHA, Miklos
Cited by 0Open access
Abstract
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.
Cite this paper
VERHOEVEN, Y., & SANTHA, M. (2005). Structural complexity and query complexity for total problems. OpenGrey (Institut de l'Information Scientifique et Technique).
VERHOEVEN, Yves, and Miklos SANTHA. “Structural complexity and query complexity for total problems.” OpenGrey (Institut de l'Information Scientifique et Technique), 2005.
VERHOEVEN, Yves, and Miklos SANTHA. 2005. “Structural complexity and query complexity for total problems.” OpenGrey (Institut de l'Information Scientifique et Technique).
VERHOEVEN, Y. and SANTHA, M. (2005) ‘Structural complexity and query complexity for total problems’, OpenGrey (Institut de l'Information Scientifique et Technique).
@misc{verhoeven2005structural,
title = {{Structural complexity and query complexity for total problems}},
author = {VERHOEVEN, Yves and SANTHA, Miklos},
journal = {OpenGrey (Institut de l'Information Scientifique et Technique)},
year = {2005}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.