| Résume | The complexity of first-order query problems has deserved a lot of attention over the last 30 years. In full generality, i.e, for arbitrary classes of structures, these problems are not tractable (under some complexity assumptions). However, when classes of structures are « sparse », very efficient algorithms can be exhibited. Going further in this direction, the tractability frontier has even been fully characterized in some contexts, for example for hereditary classes. In this talk, I will give briefly survey the role played by tameness notions coming from graph theory and model theory in the quest for complexity characterizations for some natural algorithmic tasks in logic. |
