# A Problem on Time Complexity of Algorithms

For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?

By verifying, I mean that given a candidate solution $y$, we can judge whether $y$ is correct or not in time $O(n^s)$.

• I'm not familliar with $\omega$ notation, do you mean $\Omega$ notation? May 7, 2013 at 4:42
• I edited your question to reflect your comment on the A.Schulz answer, I don't know if this edit is correct or not, but IMO Schulz answer was correct before this edit.
– user742
May 7, 2013 at 10:03
• @jmite $\omega$ notation is standard Landau notation. It is to $\Omega$ as $o$ is to $O$. May 9, 2013 at 10:55
• "Can be computed in $\omega(n^5)$ time" does not mean the same thing as "cannot be computed in $O(n^5)$ time". It is possible to buy a pencil for more than a million dollars, but that doesn't imply that I can't buy a pencil for less than a million dollars. May 9, 2013 at 14:36
• What's the quantifier on $s$? Do you mean "For all integers $s$ and $t$, is there a problem..." or do you mean "For every integer $t$, is there an integer $s$ and a problem..." or do you mean "Is there an integer $s$ such that for every integer $t$ there is a problem..."? May 9, 2013 at 14:39

## 2 Answers

For $k = \left\lceil \dfrac{r}{2} \right\rceil$, it is conjectured (and proven in some simpler models of computation by JeffE) that $r$-SUM problem has lower bounds $\Omega(n^k)$, the solution for which can be verified in $O(n)$ time.

Pick an $r$ such that $k \gt t$, implying $\omega(n^t)$ bounds.

• Where is it proven? May 8, 2013 at 18:53
• @Shayan: Did you check out the link? (click on conjectured in the answer) May 8, 2013 at 22:13
• You can find my $r$-SUM lower bound paper here and a more readable followup paper here. May 10, 2013 at 14:53
• But the answer is proved for "simpler models of computation" not generally. May 10, 2013 at 16:39

If I understood you correctly, it is okay if $s=t=1$. In this case take sorting in some comparison based model. You can verify a correct solution with $O(n)$ comparisons. On the other hand you need $\Omega(n \log n)\subsetneq \omega(n)$ comparisons to sort.

• But I want to solve it for every integer t. Not a single sample. May 7, 2013 at 9:55