Skip to main content
Loading Explore guides…
P vs NP Problem · Acedra
Home
Explore
Mathematics
P vs NP Problem
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
50 segments
Copy
Hide video
0:01
It was March of 1956, and the legendary mathematician Kurt Gödel was unknowingly about to ask what would become the biggest unsolved question in computer science. That winter, he had been pondering how a computer might automatically prove or disprove mathematical statements. Two decades prior, Alan Turing had famously shown that in general this is not possible -- no computer program can ever succeed in proving or disproving every
0:29
mathematical statement you give it. Gödel was well aware of Turing’s work, but became interested in a slightly different problem: could you make a program that always finds proofs (if they exist) within a certain length: using at most, say, 100 total letters, numbers, and symbols? And he knew the answer: yes! (Or at least in theory.) Here’s how you can do it. Say we want a proof that 42 is an even number. Well, now we can just generate all possible strings
0:59
of characters up to the desired length and check if any of them are valid proofs. Somewhere along the way, we’d stumble upon this string that says “42 = 2 x 21, so 42 is divisible by 2. Therefore, 42 is even.” The logic definitely checks out here, so the program would stop and output the proof as a result. Of course, this method is completely ridiculous -- almost all the strings are going to be utter nonsense, and not anything
1:28
that even resembles a mathematical proof. Plus, for the specific example of proving that 42 is even, anyone familiar with the concept of even and odd numbers could’ve immediately produced this proof just by unpacking the definitions. But the point is that our program needs to work correctly on all mathematical statements, most of which will be a lot more complicated. And for these more complicated statements, it’s not immediately obvious where to even start. So how
1:55
should we program the computer to go about trying to prove general propositions other than simply letting it exhaustively explore all its potential options? Now, If the computer carries out a naive brute force search, it’ll be slow to the point of uselessness: suppose we use 50 distinct characters in total. Then with a proof size of n, the total number of strings to check would be 50 times 50 times 50 times 50… 50^n -- exponentially large. With a
2:25
maximum proof size of just 10 characters, this is already a gazillion different combinations, and if you increase the limit to, say, 10000 characters, you can forget about it. The prover would be generating all strings up to 10000 characters. That means throughout its search for a proof, it would end up recreating most pieces of text you’ve ever written, most dialogues you've ever had, heck, maybe even every distinguishable thought you’ve ever had. There would be a
2:51
literally unthinkable number of possibilities to check through, and that means the number of computational steps the prover would have to take (or the runtime) would be unthinkably too big. But yet, in theory, this program solves Gödel’s question, and it would lead him to think of a straightforward yet fascinating new question, which would, even though he didn’t know it at the time, become what we now refer to as the biggest, most profound
3:17
unsolved question in computer science. Gödel posed this new question in a letter to John von Neumann, a close colleague and a highly-accomplished and well-respected mathematician of the 20th century. Gödel was heartbroken to learn that von Neumann had grown terribly ill, and he did not expect von Neumann to immediately be able to answer this question, but was rather curious to hear von Neumann’s opinion on the answer.
3:41
In simple terms, he essentially asked: “is there a faster way to automatically generate proofs? How efficient could an automated prover be in terms of the limit on the proof size? The naive program we just considered had an exponential runtime: on the order of 50^n computational steps for a proof size of n. But to Gödel, it seemed at least plausible that a runtime proportional to n or maybe n^2 might be achievable!
4:10
Expressions like n and n^2 grow at a completely negligible rate compared to any exponential function as n gets large. With our exponential-runtime solution, a 10000-character proof size was soundly out of reach. But a program with a runtime like n^2 would only need something like 10 million computational steps for the same job. With the computers we have today that could be very doable. I want to emphasize just how significant this actually is -- because the task
4:40
of determining whether a mathematical statement is true is extremely general, and if you can do it efficiently, then, as Gödel put it, “[it] would have consequences of the greatest importance!” Not only would you likely be able to solve long-standing open problems in math like the Riemann Hypothesis or the Twin Prime Conjecture, but, as just one example, with the right mathematical model, you could answer questions about how certain
5:03
protein structures fold, which would play an integral role in curing certain diseases! Now, of course Gödel did not know how to construct his hypothetical efficient automated proof machine. He just imagined that it might be possible. It’s amazing that he was even thinking about this question -- at the time, physical computers were still in their infancy! And yet, he was already pondering what the ultimate limits of computation might be. Gödel unfortunately never heard back from von
5:32
Neumann. Von Neumann’s illness had sadly continued to worsen, and about a year after Gödel’s letter, he passed away, likely from bone or prostate cancer. But, when you really interpret what Gödel was thinking, it quickly becomes apparent that he had asked the very question that perplexes the field of computer science even to this day. Fundamentally, that question is: “given a relatively short limit on the length of
5:56
a proof (as in, a proof that would be efficient to read through and check), is there also a computer program that would be able to find that proof efficiently?” In 1971, about 15 years after Gödel’s letter to von Neumann, a computer scientist named Stephen Cook would formalize this question and give it a name: P vs NP. You may have heard about P vs NP because it’s one of the Millenium prize problems, with a $1
6:23
million prize for anyone who finds a solution. But admittedly, the name P vs NP really doesn’t tell you what the problem is actually about unless you already know quite a bit on the subject. For now, what I want you to remember is that the P vs NP problem is really just the question Gödel asked, which is about the relationship between verifying a proof and finding a proof from scratch. A little later in this video, after we’ve
6:47
gone through some more concrete examples, we’ll get to what P and NP mean, and the name P vs NP will make a lot more sense at that point. With that out of the way, let me show you a type of problem that captures the essence of P vs NP very nicely. Suppose you have a bunch of dots (called “vertices”) and a bunch of lines (called “edges”) connecting pairs of vertices. This kind of structure is called a “graph” and it comes up
7:12
all the time in various computational settings. Now, say we want to color each vertex red or blue, and we want to do it in such a way that no two vertices with an edge between them have the same color. So the current coloring would not be allowed because, for instance, these two vertices have an edge between them and they’re both colored red. However if we change the colors like so, there are no such conflicts for any pair of neighboring vertices.
7:40
As you can see, for this graph, it is possible to color all of the vertices red or blue without any conflicts, and as such we’d say the graph is “2-colorable,” since we used only 2 colors. We’d call the particular assignment of colors used for the vertices a “2-coloring” of the graph. A lot of graphs are not 2-colorable. A simple example would be this triangle-shaped construction. We can start off by coloring
8:06
this vertex red and this other vertex blue, for the third vertex, we’re stuck: coloring it red causes a conflict with the other red vertex along the edge on the left, and coloring it blue causes a conflict with the other blue vertex along the edge on the right.
8:22
Since some graphs are 2-colorable and some aren’t, let’s devise an algorithm to discern between the two! One way to do it would be to simply check all possible assignments of red or blue to each vertex, and for every assignment, check if there are any conflicts. If we go through all possibilities and they each have a conflict, then the graph is not 2-colorable. But if we ever find just one assignment without any conflicts, then the graph is 2-colorable:
8:48
that assignment is a 2-coloring of the graph! Now this algorithm works, but it is wildly inefficient -- the number of possibilities to check is 2 to the power of the number of vertices, since each vertex could be one of two colors. That means the algorithm runs in exponential time, just like Gödel’s imagined automated proof checker runs in exponential time to check through all possible strings up to a certain length. Here I’m conducting the brute force search
9:17
in order of the vertices from right to left, and if you lay them all next to each other like this, you can think of the vertices as representing a binary number where red means a digit of 0 and blue means a digit of 1. So even with this relatively small graph of just 30 vertices, we essentially have to count to 1 billion in binary to run this algorithm. I’m showing 60 of those billion colorings per second, and at that rate it would take nine minutes of just watching
9:44
this go before the first vertex in the leftmost half of the vertices gets colored blue for the first time (which is why it looks like only the rightmost vertices are changing color at the moment). And for the whole graph it would take 207 days to get through all the possibilities. We definitely don’t have that kind of time to spare, given that this is only a 22-minute video! But something interesting here is that when given a 2-coloring of some graph, it’s extremely easy
10:10
to check that it’s correct -- just make sure no two neighboring vertices have the same color. And this, at its core, is what interested Gödel when he wondered about the optimal efficiency of an automated prover when you restrict the proof size. Here, the thing we’re trying to prove is whether a graph is 2-colorable, and a proof of 2-colorability, as we saw, is very short -- all the information you need is the list
10:34
of color assignments for each vertex of the graph, and once you’ve got that, you simply check that each edge connects vertices of different colors. But could it be that the very fact that the proofs to a particular problem are short means there’s also some smart way to find a solution that runs faster than exponential time? That’s what P vs NP is all about. And for the specific case of determining 2-colorability, there is an algorithm that runs faster than exponential time!
11:01
Here’s how it works: you start by picking one of the vertices to color. You can choose red or blue -- it really doesn’t matter. Now, consider all of the neighboring vertices. Those neighbors all have to be the opposite color, otherwise there would be an edge connecting two vertices of the same color, which is not allowed. And now the same goes for each of the neighbors’ neighbors, and the neighbors’ neighbors’ neighbors and so on -- you have to keep alternating red and blue.
11:29
Now if we ever find two neighbors that get colored with the same color, like we have here with the two blue vertices on the right, then we’re stuck -- they’re not allowed to be the same color, but all of our color choices for the other vertices have been completely forced, so this graph just isn’t 2-colorable. But if that never happens, for example, if we were to remove the edge creating the conflict then we’ve found a 2-coloring!
11:54
This new algorithm is a lot better -- we only have to scan through each vertex and each edge once, which means the total runtime is proportional to the size of the graph, whereas before it was exponential in the size of the graph. So for this problem, there’s an algorithm that works exponentially faster than a brute force search. But does every problem with easily-checkable solutions have a clever algorithm like this one does? To explore that question, let’s change our
12:22
problem just slightly: all we’re going to do is add one more color. So we want an algorithm that determines whether a graph can be colored with three colors such that no two connected vertices are colored the same. 3-colorability is a less-restrictive property than 2-colorability. As in, every 2-colorable graph is still 3-colorable -- just don’t use the third color. And for some graphs which are not 2-colorable, for example this triangle graph from earlier,
12:49
the addition of that third color makes it work. So actually finding a coloring has become easier. But again there are graphs which are not 3-colorable (for example, this one). So how hard is the algorithmic task of determining whether a 3-coloring is possible? Well, the brute force method of checking through all possible color assignments still works, however nothing has changed: the number of combinations is still exponential in the number of
13:15
vertices: with n vertices, now instead of 2^n it’s 3^n. So the natural question is whether there’s an efficient algorithm for 3-colorability like there was for 2-colorability? Now, not to be misleading, you can get a much more-efficient algorithm for 3-colorability than a raw brute force search by doing the same trick we did for 2-colorability: realizing that once a particular vertex is colored, then all of its neighbors have to be colored with a different color (narrowing the
13:44
options for those neighbors from three to two). And in addition, some even more clever algorithms for 3-colorability were discovered in the early 2000s, which achieve a runtime on the order of 1.3289^n. However these better approaches are still exponential time, which means they’ll be hopelessly inefficient on really big graphs. But remember, 3-colorability is just as easily-verifiable as 2-colorability: again, just make sure that all neighbors are colored
14:13
differently from each other. And yet as far as we know, determining 3-colorability is exponentially harder than determining 2-colorability. Even though both are efficiently verifiable, only for the case of 2-colorability have we also found an efficient algorithm to solve the problem in the first place. More specifically, we found an algorithm with a runtime that's a polynomial function of the size
14:39
of the input, which in general means that if n is a number representing the size of the input to an algorithm, then that algorithm’s runtime can be expressed using a formula adding together one or more powers of n, like n^2, n^3, n^2 + n^3, or 5n^4 + 17n + 47. These types of mathematical expressions are called “polynomials,” and when an algorithm’s runtime is a polynomial function of the input size, in a sense that’s what it means for the algorithm to be “efficient,” particularly
15:11
in comparison to an exponential runtime where n appears in the exponent, like 2^n for example. We saw this earlier when considering Gödel’s thought experiment: these two specific polynomial runtimes, n and n^2, need monumentally fewer computational steps to accomplish the same task as something like 2^n. And for sufficiently large values of n, any other polynomial runtime would outperform an exponential one, not just n and n^2.
15:40
When people talk about algorithms that operate on graphs, the input size is often counted separately for the number of vertices and the number of edges in the graph, but to keep things simple, think of the size as meaning the combined number of vertices and edges. In our case, the efficient algorithm for 2-colorability only needs to go through each vertex and each edge once, so if there are n total vertices and edges,
16:04
the total number of computational steps taken grows in proportion to n, which means the runtime is a polynomial where the exponent is just 1. When Stephen Cook was formalizing all of this in the 1970s, he created a classification for all problems that can be solved with a polynomial runtime, such as 2-colorability. He called this class of problems “P,” standing for polynomial-time. And Cook also created a classification called “NP” for problems
16:33
whose solutions can be verified in polynomial-time. This includes all the problems in P like 2-colorability, since you can verify the solutions to those problems in polynomial-time by just solving them in polynomial-time. But it also includes problems like 3-colorability for which actually finding a solution seems much harder than verifying one. Once more, the terminology here is a bit confusing -- NP actually stands for “Nondeterministic
17:01
polynomial-time.” The word “Nondeterministic” comes from an equivalent definition of NP that’s based on something called a “Nondeterministic Turing Machine,” but the definition I (and many others) find the most intuitive is based on the idea of verifying solutions -- again, NP really just means the class of problems for which solutions can be verified in polynomial-time. So the P vs NP question is whether any problem whose solutions can be verified efficiently
17:30
(meaning in polynomial-time) can also be solved efficiently, or in polynomial-time. In other words, is P the same as NP? Take a moment to really let that sink in -- if this were true, it would mean the ability to simply recognize a solution to a problem would mean you could solve it. For example, here’s a sudoku puzzle -- our intuition would say that solving the puzzle from scratch would probably be a lot harder
17:58
than checking that the solution is valid once everything’s filled in. In other words, our intuition is that P is different from NP. But if P is the same as NP, it would mean there’s some genius way of playing sudoku that solves the puzzle about as fast as you could check a solution -- a method that somehow forgoes the normal trial and error that you and I would use. As of today, we still don’t know the answer to the P vs NP problem:
18:26
there could be some clever way to solve sudoku and 3-colorability and multitudes of other problems in polynomial-time, but at least at the moment, we haven’t figured out how. Stephen Cook became fascinated by P vs NP, and he proved a groundbreaking result related to it: he showed that there were certain special NP problems (which he called NP-complete problems) that are in some sense the hardest to solve among all NP problems.
18:53
More specifically, a polynomial-time algorithm for any NP-complete problem could be used to manufacture a polynomial-time algorithm for any other NP problem. That’s because Cook could show that any instance of an NP problem could be transformed into an instance of an NP-complete problem -- so solving just one NP-complete problem gives you the key to solving all NP problems. In the late 60s and early 70s, Cook and a
19:21
Soviet-American computer scientist named Leonid Levin independently demonstrated that a problem called SAT (or boolean satisfiability) is NP-complete. This was the first-discovered NP-complete problem. Later in 1972, a friend and colleague of Cook named Richard Karp found a list of 20 other NP-complete problems, one of which is, surprise surprise, 3-colorability! So, as weird as it may sound, there’s a way to take any NP problem,
19:49
for example, determining whether this Sudoku puzzle has a solution, and transform it into a graph such that the puzzle has a solution if and only if the graph is 3-colorable! And a 3-coloring of the graph would encode the solution of the Sudoku puzzle. The process for how that works is called a “reduction” and it may be something I cover in a future video. But the key thing to remember is that you could transform any NP problem -- any problem whose
20:18
solutions are efficiently verifiable -- into an instance of the 3-colorability problem, SAT, or any known NP-complete problem (of which there are now thousands). This means that if you could find a polynomial-time algorithm for any NP-complete problem, P would be the same as NP -- you could solve all NP problems efficiently by just transforming them into the one you know how to solve. But we still
20:43
haven’t found a polynomial-time algorithm for any NP-complete problem, which means at least for now, they’re all outside of our grasp. In a way, it’s almost prophetic that von Neumann never got a chance to reply to Gödel’s letter in 1956 -- Gödel’s humble question turned out to be so deep that it has and will likely continue for quite some to outlive some of the greatest minds in the field, of which von Neumann was undoubtedly one.
21:08
P vs NP is in essence a question about the nature of thought itself. It asks whether discovery is fundamentally harder than recognition. If not, as Gödel wrote in his letter, “the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.” If P is the same as NP, creativity could be automated! Every proof could, in theory, be found by a sufficiently clever algorithm. And keep in mind, Gödel thought this
21:37
was a plausible reality! But if P is different from NP, which most experts believe is the case, then there are problems whose solutions we can instantly recognize, but for which no algorithm can quickly find a solution in the first place. It would mean that automating some tasks just requires brute force.
21:57
Perhaps, that’s what makes human thought so powerful: not just our ability to discern brilliance, but our mysterious, often unpredictable path to discovering it. Thanks for watching.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat