Je viens de tomber sur ce billet de Dick Lipton (dont je recommande le blog, bien que je sois loin de tout comprendre). Cela me ramène 15 ans en arrière et à des discussion avec Jacques Mazoyer, Olivier Teytaud et d'autres...

On ne connaît toujours pas la classe de complexité du problème suivant : étant donné deux tables définissant des groupes, tester si les deux groupes sont isomorphes.

C'est bien évidemment dans NP... et puis... on ne sait pas grand chose d'autre.

Entre ça et mon problème (extension de celui évoqué dans Gawlitza & Monniaux 2001) dont je ne sais pas où il se balade entre PSPACE-complet et NEXPTIME, on est bien peu de choses.