This chapter gives a motivation for adopting metaheuristic approaches for solving difficult optimization problems, i.e., those that require an exponentially increasing amount of resources as a function of the problem size in the light of computational complexity theory. After describing the basic notions of computational complexity theory, we discuss a number of possible solutions to mitigate the hardness problem and argue that, although alternate approaches do exist, none of them is as general and easily applicable as metaheuristics methods to be presented and described starting from the next chapter.