Metaheuristics are a family of algorithmic techniques that are useful for solving difficult problems. Roughly speaking, the difficulty or hardness of a problem is the quantity of computational resources needed to find the solution. When this quantity increases at a high rate with increasing problem size, in a way that will be defined precisely later, we are facing a difficult problem. The theory of the computational complexity of algorithmic problems is well known [34, 66] and, in this first chapter, we shall look at the basics and the main conclusions since these ideas are needed to understand the place of metaheuristics in this context.