Complexity Theory and Specialized Structures

Computational complexity theory classifies problems by the resources needed to solve them, and two classes are central to this classification. The class P consists of problems that can be solved in polynomial time, meaning the running time of some algorithm for the problem grows no faster than a polynomial function of the input size. The class NP consists of problems whose proposed solutions can be verified in polynomial time, even if no polynomial-time method to find those solutions is known. Within NP, a problem is called NP-complete if it is among the hardest problems in the class, in the specific sense that every other problem in NP can be transformed into it using a polynomial-time reduction; the Cook-Levin theorem, proved in the early 1970s, established the Boolean satisfiability problem as the first known NP-complete problem, and thousands of other problems have since been shown to be NP-complete by reduction from it or from one another. A problem is called NP-hard if it is at least as hard as the hardest problems in NP, without necessarily belonging to NP itself.