# Problems with proven complexity but no algorithm yet found

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.

Example:

• 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.
• Where have you looked? A simple Google query leads to promising results, in particular on cstheory.SE and Wikipedia. – Raphael Aug 29 '16 at 14:11
• @Raphael I put no constraints on it being constructive or not, but if one is already answered I'm interested in the other – GameDeveloper Aug 29 '16 at 14:13
• Yes, you are asking for problems with non-constructive complexity proofs; a constructive proof would give you an algorithm as witness. – Raphael Aug 29 '16 at 14:14