Skip to main content
2 of 2
added 270 characters in body
Richard Borcherds
  • 20.7k
  • 9
  • 97
  • 113

I suggest that a classification for finite models is in practice equivalent to a polynomial-time algorithm for the number of models of size ''n''. There are some refinements and variations of this idea: for example if the number of models of size n is polynomial in n then one would presumably want a polynomial-time algorithm that lists them all. Something like permutations are obviously classifiable in any reasonable sens, but the number of types of size n grows more than polynomially fast in n, so one cant always demand a polynomial-time listing of them.

Added later: the reason for the condition "polynomial time" rather than "enumerable" is for cases like the classification of finite simple groups, where it is trivial that the ones of order n can be effectively listed, and the problem is to do this reasonably fast.

Richard Borcherds
  • 20.7k
  • 9
  • 97
  • 113