We know that there is an algorithm for a problem that decides it in $\Omega(2^n)$ time. We know that it is not in P class, or we cannot decide?

I know that exists problems that surely cannot be decided in polynomial time because P class doesn't equal with EXPTIME (for example Go, generalized chess etc.). But I assume that there may be problems for which we currently only have an algorithm with exponential time complexity and yet can be solved in polynomial time.

• "I assume that there may be problems for which we currently only have an algorithm with exponential time complexity and yet can be solved in polynomial time" Many such examples existed across the history, indeed. E.g. convex optimization before ellipsoid method. And it would be reasonable to believe that the set of such problems is not exhausted. Jan 26 at 16:30

Well, there is a sorting algorithm that takes $$\Omega(n!)$$ steps on average: Create a random permutation of your data, check whether the resulting array is sorted, and repeat until it is sorted. But obviously the problem can be solved in $$O(n^2)$$ and practically in $$O(n \log n)$$.