| Résume | In the quest of a better understanding of Computational complexity, Descriptive complexity aims to characterize complexity classes through the lense of Logic. In particular, the main open problem in the field is to find a logic (that is, a recursive language that defines classes of structures) that captures Polynomial Time (that is, a class of structures is definable in this logic iff it is decidable in polynomial time). One of the main difficulties in that regard is to preserve isomorphism-invariance in a language designed to capture a notion of computation. To address this, it is natural to apply the framework of permutation groups, and computational group theory, as those tools are known to be connected to the complexity of the Structure Isomorphism problem (which is equivalent to the Graph Isomorphism problem). After a brief overview of the connection between permutation groups and isomorphism-invariance, I will present an application of permutation group theory to the quest of a logic for PTIME, namely the design of an operator extending the expressive power of Fixed-Point Logics. Then I will explore a few ways in which this framework can be useful in the study of Choiceless Polynomial Time. |
