NP-complete impossible to solve in $O(n)$ NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small $d$? Say, has anybody proved that it's impossible to solve subset sum in $O(n)$?
Suppose that somebody had proved it for $O(n^d)$. Now assume $P = NP$ and fix some $NP$-complete problem that has a $O(n^r)$-time solution with $r &gt; d$. If you pad the input of every instance, raising input length from $k$ to $k^{r/d}$ then the original algorithm works but the solution is produced in time $O((n^r)^{d/r}) = O(n^d)$, a contradiction.

In short: no. A proof that no $NP$-complete problem can have a $O(n^d)$-time solution is a proof that $P \neq NP$.

Edit: The link in zarathustra's comment frames your question in a way that avoids this kind of cheap padding trick.
Suppose that somebody had proved it for $O(n^d)$. Now assume $P = NP$ and fix some $NP$-complete problem that has a $O(n^r)$-time solution with $r &gt; d$. If you pad the input of every instance, raising input length from $k$ to $k^{r/d}$ then the original algorithm works but the solution is produced in time $O((n^r)^{d/r}) = O(n^d)$, a contradiction.

In short: no. A proof that no $NP$-complete problem can have a $O(n^d)$-time solution is a proof that $P \neq NP$.

Edit: The link in zarathustra's comment frames your question in a way that avoids this kind of cheap padding trick.