P and NP - Understanding the Complexity of Algorithms

When we talk about the difficulty of algorithms, two letters show up again and again: P and NP. These are names for classes of problems, grouped by how much time their best algorithms need as the input grows. In this post, we will look at what P, NP, NP-complete and NP-hard actually mean, and how they relate to algorithmic complexity.

First, what do we mean by “complexity of a problem”? In computer science, the complexity of a problem is about how much time or memory any algorithm would need to solve it, as a function of the input size. We are not only judging a single algorithm, but also asking “could there exist a fundamentally faster one?”

A common way to classify problems is by using three related notions: P, NP, and NP-hard. From these, we also get NP-complete problems, which sit at the center of the famous “P vs NP” question.

A problem is in the class P if there is an algorithm that can solve every instance of the problem in polynomial time. That means the running time is bounded by some polynomial in the input size, for example n² or n³. Roughly speaking, these are the problems we consider “efficiently solvable.” Many classic algorithms fall into P, such as mergesort and quicksort for sorting, or Dijkstra’s algorithm for single-source shortest paths in graphs with non-negative edge weights.

A problem is in the class NP if, whenever the correct answer is “yes,” there exists a solution that can be checked in polynomial time. The name stands for “nondeterministic polynomial time.” Another equivalent way to think about NP is: these are the problems that could be solved in polynomial time by a nondeterministic machine that can magically “guess” a candidate solution and then verify it quickly. We do not necessarily know how to find that solution efficiently, but if someone hands us a candidate, we can verify it efficiently. Decision versions of the traveling salesman problem, knapsack, and graph coloring are classic NP problems.

A problem is NP-hard if it is at least as hard as every problem in NP, in the sense that any NP problem can be transformed, or reduced, to it using a polynomial-time transformation. If you could solve an NP-hard problem efficiently, you could solve every problem in NP efficiently as well. NP-hard problems do not need to be in NP themselves; they may not even be decision problems or may be undecidable. Examples that are both NP-hard and in NP (that is, NP-complete) include the Boolean satisfiability problem (SAT) and the clique decision problem in graphs.

NP-complete problems are a special subset of NP. A problem is NP-complete if it is in NP and it is NP-hard. These are the “hardest” problems inside NP: if you find a polynomial-time algorithm for any one NP-complete problem, then all NP problems become solvable in polynomial time too.

This leads to one of the most important open questions in theoretical computer science: is P equal to NP? If P = NP, it would mean that every problem whose “yes” answers can be verified in polynomial time can also be solved in polynomial time. A huge number of problems we currently believe to be intractable would suddenly become efficiently solvable. Cryptography, optimization, scheduling, and many other fields would be affected in a deep way. On the other hand, if P ≠ NP, then there exist problems whose solutions are easy to check but fundamentally hard to find.

Formally, these classes and completeness notions are defined for decision problems, which return a yes or no answer. In practice, many optimization problems are studied by looking at their decision versions. For example, instead of asking “what is the minimum cost of a traveling salesman tour?”, we ask “does there exist a tour of cost at most K?”. Complexity results for the decision version usually tell us a lot about how hard the corresponding optimization problem is, and many optimization problems have NP-hard or NP-complete decision versions.

To summarize: P is the class of problems we know how to solve efficiently. NP is the class of problems whose “yes” answers we can verify efficiently. NP-complete problems are the hardest problems inside NP, and NP-hard problems are at least as hard as those. The question P vs NP asks whether “efficiently solvable” and “efficiently verifiable” are in fact the same.

The answer to that question is still unknown, and whatever it turns out to be will reshape how we think about algorithms and computational difficulty.