We can use the notion of efficient algorithms to categorize problems: a hard problem is one that has no efficient (polynomial-time) algorithm. (This is ``algorithms as a taxonomic tool!'')
A natural question to ask is: Are there any hard problems?
Yes. You can study them (EXP-hard problems) in the complexity course. In fact, there are some problems whose answers cannot be computed!
Amazingly, there is a huge class of important problems whose status as hard or easy is unknown. What we do know is that they are all easy or all hard!
These are the NP-complete problems. Today will be a quick survey of why these problems are important in the study of algorithms. Next time we'll look at developing algorithms for NP-complete problems.
