Guillaume Bonfante (LORIA, Nancy)

La complexité implicite des calculs vise à décrire des classes de fonctions sans références à une notion de machine. De ce fait, elle place en son coeur la notion d’algorithme. Nous illustrerons quelques idées de la complexité implicite dans des cas concrets, en décrivant le temps polynomial par exemple. Et puis vient la question, comment distinguer des ensembles d’algorithmes? Nous reviendrons sur le sujet en nous appuyant sur le non-déterminisme.