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 2 Décembre 2003

La conjecture du spectre et la conjecture de Ash, derniers développements

par Annie Chateau (LLAIC, Université d'Auvergne)

Nous étudions une conjecture énoncée en 1994 par Ash, liée à une conjecture énoncée par Asser en 1955, la conjecture du Spectre. Celle-ci est équivalente à la conjecture NE=?CoNE en complexité. Le destin de cette conjecture est lié à celui de la célèbre conjecture P=NP, car si NE!=CoNE, alors P!=NP. Le spectre d'un énoncé est l'ensemble des cardinaux des modèles finis de cet énoncé, et la conjecture du Spectre consiste en l'affirmation "Le complémentaire d'un spectre est un spectre".

La conjecture de Ash implique la conjecture du Spectre, mais l'autre implication n'est pas vraie. Nous avons dégagé une condition nécessaire et suffisante dérivée de la conjecture de Ash, appelée "conjecture de Ash ultrafaible".

Nous avons mis en place un plan d'attaque de la conjecture du Spectre en sélectionnant certains cas particuliers, ainsi que des cas restreints qui sont équivalents au cas général. Nous présentons dans cet exposé les différentes conjectures, les restrictions pour lesquelles nous disposons de résultats, ainsi que les perspectives d'extension de ces résultats.

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