There are cases where the lower bound to solve some problems (e.g. sorting) have been proved to be less than any known algorithm at the time. If you prove that

There are cases where the lower bound to solve some problems (e.g. sorting) have been proved to be less than any known algorithm at the time. If you prove that the lower bound for any NP-Complete problem is O(p) where p is a polynomial, then P=NP and you do not necessarily have the algorithm. http://en.wikipedia.org/wiki/Upper_and_lower_bounds http://en.wikipedia.org/wiki/Upper_and_lower_bounds