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)$.

  • $\begingroup$ I'm not familliar with $\omega$ notation, do you mean $\Omega$ notation? $\endgroup$ May 7, 2013 at 4:42
  • $\begingroup$ 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. $\endgroup$
    – user742
    May 7, 2013 at 10:03
  • $\begingroup$ @jmite $\omega$ notation is standard Landau notation. It is to $\Omega$ as $o$ is to $O$. $\endgroup$
    – Pål GD
    May 9, 2013 at 10:55
  • 1
    $\begingroup$ "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. $\endgroup$
    – JeffE
    May 9, 2013 at 14:36
  • 3
    $\begingroup$ 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..."? $\endgroup$
    – JeffE
    May 9, 2013 at 14:39

2 Answers 2


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.

  • $\begingroup$ Where is it proven? $\endgroup$
    – Shayan
    May 8, 2013 at 18:53
  • 4
    $\begingroup$ @Shayan: Did you check out the link? (click on conjectured in the answer) $\endgroup$
    – Aryabhata
    May 8, 2013 at 22:13
  • 2
    $\begingroup$ You can find my $r$-SUM lower bound paper here and a more readable followup paper here. $\endgroup$
    – JeffE
    May 10, 2013 at 14:53
  • $\begingroup$ But the answer is proved for "simpler models of computation" not generally. $\endgroup$
    – Shayan
    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.

  • 1
    $\begingroup$ But I want to solve it for every integer t. Not a single sample. $\endgroup$
    – Shayan
    May 7, 2013 at 9:55

Your Answer

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

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