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.
Problems with proven complexity but no algorithm yet found
algorithms;complexity theory