The famous P = NP conjecture states that the hardest problems in NP do not admit polynomial-time algorithms and are thus not contained in P. Although this statement remains unproven, it is widely believed to be true. Hardness of a problem for a particular class intuitively means that the problem is no easier than any other problem in that class. Both membership and hardness are established in terms of reductions that transform instances of one problem into instances of another problem using computational means appropriate for the complexity class under consideration. Most reductions in this book rely on reductions that can be computed in time polynomial in the size of the problem instances, and are called polynomial-time reductions. Finally, a problem is said to be complete for a complexity class if it is both contained in and hard for that class. For instance, deciding whether a directed graph possesses a Hamiltonian cycle is NP-complete