Finite simple groups and complexity class NP

Abstract: This talk will describe connections between structural results about the finite simple groups and the complexity of computational algorithms for permutation groups.

The first part of the talk will discuss the base size of a permutation group, an invariant which determines the complexity of many permutation group algorithms. We will present a new, optimal, bound on the base size of the primitive groups that are not large base. After this, we will discuss some group-theoretic questions for which there is no known polynomial time solution. In particular, we shall present a new approach to computing the normaliser of a primitive group $G$ in an arbitrary subgroup $H$ of $S_{n}$. Our method runs in quasipolynomial time $O(2^{log^3 n})$, whereas the previous best known algorithm required time $O(2^n)$.

This is partly joint work with Mariapia Moscatiello (Padova), and partly with Sergio Siccha (Siegen).

group theory

Audience: researchers in the topic

GOThIC - Ischia Online Group Theory Conference

Series comments: Please send a message to andrea.caranti@unitn.it to receive a link to the Zoom room where the conference (a series of talks, actually) takes place.