La fin d'année approche, et, comme annoncé précédemment, ce jour est le dernier pour transmettre au secrétariat vos demandes de commandes ou de mission pour 2019. Pensez-y !
Plusieurs évènements du laboratoire à ne pas râter dont le pot de départ et de succès d'Etienne, et la journée autour des algorithmes de Claire avec pas moins de 7 intervenantes (inscriptions bientôt closes car la salle est déjà quasi-complète !).
Notez aussi une réunion d'information sur la réforme des retraites dans notre bâtiment mardi prochain.
Enfin, vous trouverez aussi un double courrier du CNRS au sujet des ERC : une réunion au siège du CNRS et en visio est prévue le 17 décembre. Je joins aussi quelques lettres des partenaires afin que vous puissiez y souscrire si vous le souhaitez.
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, the polynomial hierarchy is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods. The first main result of descriptive complexity was Fagin's theorem (1974). It established that NP is precisely the set of languages expressible by sentences of existential second-order logic. Many other classes were later characterized in such a manner.
Plus d’informations sont fournies dans les liens ou les pièces attachées.