<p>The algorithmic problem is to tell if two finite groups (given by their multiplication tables) are isomorphic.</p>
<p>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.</p>

CC BY-SA 4.0
2021-04-27T16:09:42.263Z
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.)
Joshua Grochow
CC BY-SA 4.0
2021-04-26T10:05:18.187Z
2021-04-26T10:05:18.187Z
neinoa
<p>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 <span class="math-container">$n_1, n_2, n_3, \dots$</span> and want to show that one cannot solve the NP-hard problem in polynomial time when restricted to inputs of sizes <span class="math-container">$n_i$</span>.</p>
<p>A naive idea to prove the statement would be to take an instance of size <span class="math-container">$n$</span>, &quot;pad&quot; it to the next largest value <span class="math-container">$n_i$</span> and solve it in <span class="math-container">$n_i^{O(1)}$</span>. However, this creates no contradiction, because it could be that the <span class="math-container">$n_i$</span> are spaced so far apart that the next largest <span class="math-container">$n_i$</span> is exponential in <span class="math-container">$n$</span>.</p>
<p>It appears to me that this question is not related to <a href="https://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html" rel="nofollow noreferrer">Mahaney's theorem</a>, since for a given <span class="math-container">$n_i$</span> we allow <em>all</em> instances of size <span class="math-container">$n_i$</span>, not just a sparse subset.</p>
<p>I am not fixed on the classes P and NP. A similar hardness result for other classes would also be highly appreciated.</p>

CC BY-SA 4.0
2021-04-26T10:05:46.837Z
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}$.
Emil Jeřábek
CC BY-SA 4.0
2021-04-26T10:26:04.887Z
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
CC BY-SA 4.0
2021-04-26T17:46:55.917Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/123461/discussion-between-albert-hendriks-and-emil-jerabek).
Albert Hendriks
<cc.complexity-theory><reference-request>
Hardness when restricted to an infinite number of far apart instance sizes
Jan
# Hardness when restricted to an infinite number of far apart instance sizes

(Asked by: username_0 on 2021-04-26)

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](https://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html), 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.

**Tags:** cc.complexity-theory, reference-request

> **Comments:**
> **username_1**: 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}$.  
> **username_0**: 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.  
> **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/123461/discussion-between-albert-hendriks-and-emil-jerabek).  

---

## 1 answers

### Answer by username_3 on 2021-04-26. Score: 1

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.

> **Comments:**
> **username_4**: 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.)  

---

