Navigation – Plan du site

AccueilNuméros135Valeurs extrémales d'un problème ...

Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale

Extremal values of a combinatorial optimization problem and polynomial approximation
Marc Demange et Vangelis-Th. Paschos

Résumés

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.

Haut de page

Pour citer cet article

Référence électronique

Marc Demange et Vangelis-Th. Paschos, « Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale »Mathématiques et sciences humaines [En ligne], 135 | Automne 1996, mis en ligne le 10 février 2006, consulté le 18 octobre 2021. URL : http://journals.openedition.org/msh/2713 ; DOI : https://doi.org/10.4000/msh.2713

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page
  • OpenEdition Journals
Search OpenEdition Search

You will be redirected to OpenEdition Search