Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale
Demange, Marc; Paschos, Vangelis (1996), Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale, Mathématiques, Informatique et Sciences Humaines, 135
Type
Article accepté pour publication ou publiéDate
1996Nom de la revue
Mathématiques, Informatique et Sciences HumainesVolume
135Éditeur
EHESS
Métadonnées
Afficher la notice complèteRésumé (FR)
A la suite de quelques-uns de nos travaux antérieurs sur la théorie de la complexité et de l'approximation polynomiale, nous présentons quelques nouvelles réflexions et arguments sur les valeurs (et solutions) extrémales, (optimale et pire), des problèmes d'optimisation combinatoire. Cette discussion nous conduit à considérer la limite entre constructibilité et non-constructibilité, source constante de contradiction en théorie de la complexité. En effet, cette théorie, telle qu'on la connaît et manie aujourd'hui, est fondée sur la non-constructibilité tandis que deux de ses domaines principaux, l'optimisation combinatoire et la théorie de l'approximation polynomiale, nécessitent un cadre conceptuel fondé sur la constructibilité. L'approximation polynomiale dépasse aujourd'hui sa conception originelle (en tant qu'ensemble d'outils pour la résolution rapide des problèmes NP-complets), intervient très fortement dans la définition de nouvelles notions et objets mathématiques et fait ainsi partie à part entière de "l'arsenal" de la complexité. Elle est un outil théorique majeur pour l'appréhension, l'approfondissement et l'enrichissement de la théorie de la complexité et notamment de la connaissance de la classe NP. Ces développements récents de l'approximation polynomiale dévoilent des problèmes particulièrement intéressants, notamment d'un point de vue épistémologique.Mots-clés
Combinatoire; Algorithmes - AlgorithmiquePublications associées
Affichage des éléments liés par titre et auteur.
-
Demange, Marc; Paschos, Vangelis (1993) Article accepté pour publication ou publié
-
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis (1994) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1996) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (2000) Document de travail / Working paper
-
Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié