Hard Problems

For most of the problems that we have seen in our study of algorithms, we have seen polynomial time algorithms. Polynomial time algorithms are generally considered to be fairly efficient. For many of the simple algorithms we've seen (searching, sorting, etc.), we are used to seeing logarithmic or linear algorithms, and consider polynomial time algorithms (e.g., selection sort as an $$O(n^2)$$ algorithm) to be inefficient. However, for more complex, real-world problems (especially with graphs), polynomial time algorithms are considered fairly efficient.

As seen in the previous lesson, the traveling salesman problem is a hard problem to solve. In fact, it is an intractable problem -- a problem for which no known polynomial time algorithm exists.

To learn more about this and other, similar hard problems, watch the following videos: