Jean-Marie Le Bars (GREYC)

Lorsque la proportion de graphes a n sommets qui sont modeles d’une propriete P a une limite quand n tends vers l’infini, cette limite est appelee probabilite asymptotique de P.

Une logique L admet une loi 0-1 quand toute propriete P exprimable dans L a une probabilite asymptotique egale a 0 ou 1.

La logique du premier ordre admet une loi 0-1 contrairement a la logique existentielle du second ordre. Cependant certains fragments de celle-ci verifient une loi 0-1.

Nous verrons qu’une variante de la propriete de noyau, propriete NP-complete exprimable avec seulement deux variables du premier ordre, permet de caracteriser les fragments pour lesquels la loi 0-1 n’est pas verifiee.

Ce resultat etait tout a fait inattendu car il enfreint une correspondance precedemment etablie par les chercheurs de ce domaine entre decidabilite et lois 0-1.