Résumé de séminaire

Résumé :

Un des buts de la théorie de la complexité est de déterminer la difficulté intrinsèque des problèmes. Pour cela on cherche à obtenir des bornes de complexité inférieures et supérieures les plus proches possibles. A l'heure actuelle, les seules bornes inférieures obtenues pour des problèmes P ou NP sur des modèles de calcul généraux sont des bornes mixtes temps-espace, c'est-à-dire pour lesquelles le temps et l'espace à la fois sont restreints, et uniquement pour des problèmes bien précis. Ainsi, une étude détaillée des classes de complexité mixte semble nécessaire si l'on souhaite obtenir de nouvelles bornes inférieures, ou généraliser celles déjà connues à des classes entières de problèmes. On étudie les classes mixtes polynomiales NTIMESPACE(n^t,n^s), c'est-à-dire celles où le temps est en O(n^t) et l'espace en O(n^s). On donne une caractérisation logique de ces classes, ce qui démontre leur robustesse et permettra d'obtenir des problèmes complets pour ces classes.

Références :

Home page : http://users.info.unicaen.fr/~pchapdel/