 basic concepts of the theory of computational complexity, with special emphasis on decision problems, polynomial-time algorithms, and NP-complete problems. The chapter concludes with a discussion of solution approaches for NP-hard problems, introducing constructive heuristics, local search