Does there exists a computable problem P such that:

  • Is proven that P can be solved with an algorithm that has a certain complexity.
  • The best algorithm know unluckily is still slower (greater complexity) than the proven bound.


  • A problem that we have proven can be solved in worst case in $O(n^2)$ operations.
  • The best algorithm that's currently known runs in $\Omega(n^3)$ time.
  • 3
    $\begingroup$ Where have you looked? A simple Google query leads to promising results, in particular on cstheory.SE and Wikipedia. $\endgroup$ – Raphael Aug 29 '16 at 14:11
  • $\begingroup$ @Raphael I put no constraints on it being constructive or not, but if one is already answered I'm interested in the other $\endgroup$ – GameDeveloper Aug 29 '16 at 14:13
  • 2
    $\begingroup$ Yes, you are asking for problems with non-constructive complexity proofs; a constructive proof would give you an algorithm as witness. $\endgroup$ – Raphael Aug 29 '16 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.