3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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}$. $\endgroup$
    – Emil Jeřábek
    Apr 26, 2021 at 10:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jan
    Apr 26, 2021 at 10:26
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Albert Hendriks
    Apr 26, 2021 at 17:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Joshua Grochow
    Apr 27, 2021 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.