In what sense is the classification of all finite groups "impossible"? I think there is a general belief that the classification of all finite groups is "impossible". I would like to know if this claim can be made more precise in any way. For instance, if there is a subproblem of the classification problem that is already equivalent to an already agreed-upon wild problem. 
 A: There is a standard definition of a linear algebra problem being "wild" if it is harder than the problem of classifying a pair of matrices up to simultaneous conjugation. The classification of finite groups contains many subproblems which are expressible by linear algebra and thus I think this is a good measure. In particular, the classification of 7-step nilpotent Lie algebras is wild (I hear). If we restrict the characteristic to be sufficiently large compared to the dimension, and impose the requirement that all elements are $p$-torsion, probably the classification of such $n$-step nilpotent finite groups is the same as the classification of $n$-step nilpotent Lie algebras, thus wild, but finite $p$-groups are generally harder. Also, the classification of $n$-step nilpotent Lie algebras over $\mathbb Q_p$ probably casts a shadow over the classification of n-step nilpotent $p$-groups with bounded number of generators and sufficiently large exponent.
A: One can make the argument by wildness much more concrete than in the previous answer:  Sergeichuk ["Classification of metabelian p-groups", in: Matrix problems, Inst. Mat. Ukrain. Akad. Nauk, Kiev, 1977, pp. 150-161, in Russian] showed that isomorphism of 2-step nilpotent p-groups is already wild (over $\mathbb{F}_p$), whenever the center is not cyclic of order p.
To answer David Harden's question from the comments, which also gets at Timothy Chow's point about computational complexity: simultaneous conjugacy of k-tuples of matrices can be solved in polynomial time [Sergeichuk; Brooksbank-Luks; Chistov-Ivanyos-Karpinski] (or, I believe, even in $\mathsf{NC}$, depending on the field and model of computation; an even simpler algorithm puts it in $\mathsf{RNC}$). However, the problem of isomorphism of 2-step nilpotent $p$-groups is Tensor Isomorphism-complete G-Qiao. Another TI-complete problem is conjugacy of $k$-dimensional subspaces of matrices. Belitskii and Sergeichuk showed that the latter classification problem is strictly harder than $k$-tuple conjugacy (that is, subspace conjugacy contains k-tuple conjugacy but not conversely). When the subspaces are given by a spanning set, subspace conjugacy is at least as hard as Graph Isomorphism [Chapter 4 here contains a freely available and more complete version] (that is, Graph Iso reduces to subspace conjugacy in polynomial time), which is not known to be in $\mathsf{P}$. It is even harder than Code Equivalence (which itself is thought to be harder than Graph Iso).
