# 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$$, "pad" 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.

• In order to make the question interesting, you should formulate it so that you cannot solve the problem in time $n_i^{O(1)}$ on instances of size at most $n_i$, for each $i$. Otherwise, you can construct trivial counterexamples: for example, the language $\{w\#^i:w\in\mathrm{SAT},|w|+i\text{ is even}\}$ is NP-complete, but it can be solved in polynomial time on all odd-length instances. With the indicated correction, the notion is stable under polytime reductions, hence the question becomes equivalent to $\mathrm{NP\nsubseteq\text{i.o.-}P}$. Apr 26, 2021 at 10:05
• Thank you, Emil. Yes, it should be at most $n_i$. Thanks for pointing me to the notion of infinitely often P (i.o.-P). That's exactly what I was looking for.
– Jan
Apr 26, 2021 at 10:26
• Apr 26, 2021 at 17:46

• While this is an interesting example (and a favorite of mine), it's not really a standard complexity-theoretic assumption to assume that Group Isomorphism is not in P. (Also, by the way, Dietrich & Wilson showed that Group Isomorphism is solvable in polynomial time for all groups whose orders are in a set $S \subseteq \mathbb{N}$ of positive density.) Apr 27, 2021 at 16:09