P vs. NP

What "$P$" Means

The "$P$" in "$P = NP$" refers to the set of problems that can be solved in polynomial time.

As a rule of thumb, if an algorithm's time complexity ↴

For example, $O(n)$, $O(n^2)$, or even $O(n^{24})$ are polynomial time. A time complexity of $O(\lg(n))$ would also be polynomial time. Remember, big O bounds are upper bounds, so any algorithm that is $O(n\lg(n))$ is also $O(n^2)$, which is polynomial. A time complexity of $O(2^n)$, $O(n^n)$, or $O(n!)$ would not be polynomial time.

With this definition, algorithms like insertion sort ($O(n^2)$), binary search ($O(\lg(n))$), Dijkstra's algorithm ($O((N+M)\lg(N))$) are said to be "in $P$." Some other algorithms like the knapsack problem, where we don't have a polynomial time algorithm, may or may not be "in $P$." (We can't say they're not in $P$, since maybe there's a clever polynomial time algorithm to solve them that we haven't found yet.)

Does $P = NP$?

What's the relationship between $P$ and $NP$?

First, any problem in $P$ is also in $NP$. If we can solve a problem in polynomial time, then we can verify a solution to the problem by solving it (in polynomial time) and comparing our answer to the provided one.

The big question is, are there problems that are in $NP$ that are not in $P$?

In other words, is $P$ a smaller circle inside of $NP$?

Or are they the same circle?

We don't know.

There are lots of problems that we know are in $NP$ where we don't have polynomial time algorithms for them. But we don't know if that's because there aren't any polynomial time algorithms or if that's because we just haven't found them yet.

So, when someone asks if "$P = NP$," they're really asking if there are problems that are easy to verify but hard to solve.

$NP$ Complete Problems

How can we show if a problem is $NP$ complete?

The first property is usually straightforward: given an answer to the problem, show how you could check that answer in polynomial time.

To show the second property, take an existing $NP$ complete problem (like graph coloring or SAT) and show how you could transform that problem into your new problem. As an example, to show that the knapsack problem is NP complete, you could show how a graph coloring problem could be transformed into the knapsack problem.

At a high level, we're building out a chain of transformations, showing how we can take one problem and reshape it as a different one. SAT is at the root of our chain and other problems follow.

If we can add a $NP$ problem to the chain, we know it's $NP$ complete.

Some Famous $NP$ Complete Problems

Which problems are known to be $NP$ complete? Here are some of the big ones:

• SAT : Determining if a boolean formula can be satisfied.
• Graph Coloring : Determining if a graph has a valid coloring with $k$ colors.
• The Knapsack Problem : Figuring out the maximum value we can fit in a knapsack with a specific weight capabity.
• Traveling Salesman Problem: Determining if there's a path through a graph that visits every node exactly once.

What's interesting here is that, at the surface, these problems all seem very different. The fact that they're $NP$ complete means that a polynomial time solution for any of them would provide a polynomial time solution for all of them. In some sense, they're all the same really hard problem.

What if $P = NP$?

So, does $P$ equal $NP$?

It's still an open question, but most researchers think $P$ doesn't equal $NP$.

Given the number of $NP$ complete problems and the fact that they cross so many different areas of computer science, it seems unlikely that we would not have found a polynomial time solution for any of them if $P$ did equal $NP$.

If $P$ did equal $NP$, it would have profound impacts on society. Many optimization problems that are currently too slow to solve in practice, like the traveling salesman problem or knapsack problem, would become feasible. Additionally, public-key cryptography, which is used in things like HTTPS, relies on the fact that splitting a large number into its factors is computationally difficult. If $P$ equals $NP$, breaking encryption would be feasible, and the entire internet security framework would need to be reworked.

That said, we haven't been able to prove that $P$ doesn't equal $NP$. It's still an open question.