patternModerate
Why are most (or all?) polynomial time algorithms practical?
Viewed 0 times
whypolynomialarealltimealgorithmspracticalmost
Problem
I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{999999999999999999999})$ is polynomial time, but not efficient). Yet, isn't it the case that all algorithms in polynomial time also happen to be realistic, like at most $O(n^4)$ or something? I guess my questions are:
-
Is this surprising?
-
Are there any examples of algorithms that are polynomial time but not practical?
-
Is this surprising?
-
Are there any examples of algorithms that are polynomial time but not practical?
Solution
The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all:
-
The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice.
-
The AKS primality testing algorithm runs in polynomial time but is too slow to be practical. Instead, randomized polynomial time algorithms are used. We sacrifice certainty for performance.
-
Fast matrix multiplication algorithms run asymptotically faster than high-school matrix multiplication (both are polynomial), but are too slow to be practical. The high-school algorithm is used in practice.
-
A similar issue occurs in fast integer multiplication algorithms. The algorithm with the best asymptotic complexity, Fürer's algorithm, is too slow to be used in practice. Instead, relatively simple algorithms are used even for quite large integers.
-
Big data algorithms need to run in linearithmic time (which is $O(n
\log^{O(1)}n)$) to be practical.
These examples show that the identification of polynomial time with practical is not accurate, and might depend on the circumstances. Researchers in theoretical algorithms feel a need to justify their field of research, and so they ideologically believe in the sentiments expressed in the comment you mention. You shouldn't take such comments too literally.
In fact, many algorithms used in practice are heuristic and we don't have any estimates on their running time other than empirical results. Such algorithm don't fit into the theoretical framework at all, yet there are very useful in practice. Several (but not all) machine learning algorithms belong to this class just in terms of running time (not to mention in terms of performance), as do search algorithms such as A* and alpha-beta, and SAT solving algorithms.
-
The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice.
-
The AKS primality testing algorithm runs in polynomial time but is too slow to be practical. Instead, randomized polynomial time algorithms are used. We sacrifice certainty for performance.
-
Fast matrix multiplication algorithms run asymptotically faster than high-school matrix multiplication (both are polynomial), but are too slow to be practical. The high-school algorithm is used in practice.
-
A similar issue occurs in fast integer multiplication algorithms. The algorithm with the best asymptotic complexity, Fürer's algorithm, is too slow to be used in practice. Instead, relatively simple algorithms are used even for quite large integers.
-
Big data algorithms need to run in linearithmic time (which is $O(n
\log^{O(1)}n)$) to be practical.
These examples show that the identification of polynomial time with practical is not accurate, and might depend on the circumstances. Researchers in theoretical algorithms feel a need to justify their field of research, and so they ideologically believe in the sentiments expressed in the comment you mention. You shouldn't take such comments too literally.
In fact, many algorithms used in practice are heuristic and we don't have any estimates on their running time other than empirical results. Such algorithm don't fit into the theoretical framework at all, yet there are very useful in practice. Several (but not all) machine learning algorithms belong to this class just in terms of running time (not to mention in terms of performance), as do search algorithms such as A* and alpha-beta, and SAT solving algorithms.
Context
StackExchange Computer Science Q#52164, answer score: 10
Revisions (0)
No revisions yet.