Hardness when restricted to an infinite number of far apart instance sizes
The algorithmic problem is to tell if two finite groups (given by their multiplication tables) are isomorphic.
It is not known if this can be solved in polynomial time in the cardinality of the group. But for groups of prime order this can be solved in constant time.