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.