1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ "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. $\endgroup$
    – rus9384
    Jan 26 at 16:30

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.