Hardness when restricted to an infinite number of far apart instance sizes Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance sizes? To be precise, I have an infinite ascending sequence of numbers $n_1, n_2, n_3, \dots$ and want to show that one cannot solve the NP-hard problem in polynomial time when restricted to inputs of sizes $n_i$.
A naive idea to prove the statement would be to take an instance of size $n$, &quot;pad&quot; it to the next largest value $n_i$ and solve it in $n_i^{O(1)}$. However, this creates no contradiction, because it could be that the $n_i$ are spaced so far apart that the next largest $n_i$ is exponential in $n$.
It appears to me that this question is not related to Mahaney's theorem, since for a given $n_i$ we allow all instances of size $n_i$, not just a sparse subset.
I am not fixed on the classes P and NP. A similar hardness result for other classes would also be highly appreciated.
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.