Of course, this formal use of "intractable" should be viewed only as a rough approximation to its dictionary meaning. The distinction between "efficient"polynomial time algorithms and "inefficient" exponential time algorithms admits of many exceptions when the problem instances of interest have limited size. Even in Figure 1.2, the 2ⁿ algorithm is faster than the n⁵ algorithm for n < 20. More extreme examples can be constructed easily.

Furthermore, there are some exponential time algorithms that have been quite useful in practice. Time complexity as defined is a worse-case measure, and the fact that an algorithm has time complexity 2ⁿ means only that at least one problem instance of size n requires that much time. Most problem instances might actually require far less time that that, a situation that appears to hold for several well-known algorithms. ... branch-and-bound algorithms for the knapsack problem have been so successful that many consider it to be a "well-solved" problem, even though these algorithms, too, have exponential time complexity.

Unfortunately, examples like these are quite rare. Although exponential time algorithms are known for many problems, few of them are regarded as being very useful in practice. Even the successful exponential time algorithms mentioned above have not stopped researchers from continuing to search for polynomial time algorithms for solving these problems. Infact, the very success of these algorithms has led to the suspicion that they somehow capture a crucial property of problems whose refinement would lead to still better methods. So far, little progress has been made toward explaining this success, and no methods are known for predicting in advance that a given exponential time algorithm will run quickly in practice.