Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 1 Juin 2004

Extension de la méthode de Ash pour la logique existentielle du second-ordre

par Malika More (LLAIC, Université d'Auvergne)

La notion de k-quivalence d'Ehrenfeucht-Fraïssé a été utilisée par Ash pour apporter un nouvel éclairage sur la question NE=co-NE, vue sous l'angle de la complexité descriptive.

Dans une premire partie, j'exposerai cette problématique, puis j'envisagerai l'extension de cette approche l'étude de la question NP=co-NP.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr