0:00This video is about what P and NP mean. We start with one small problem, called subset sum.
0:07You're given some numbers and a target, and the question is whether some of them sum to the target. Here it's nine.
0:13These are our six numbers, and each one can be used at most once.
0:16The obvious way to find out is to try the subsets. Let's look at a short program that does exactly that.
0:24This is the whole program. Two functions, and a few lines at the bottom that use them.
0:29The first function is the solver. It works through the subsets by size: the empty one, then every single number, then every pair, and so on.
0:38For six numbers that's sixty four subsets, and for n numbers it's two to the n. That's the size of this search. It doesn't prove that every method has to look at all of them.
0:48When a subset sums to the target, the solver returns the positions of the numbers it used. If none does, it returns None.
0:56The second function doesn't search. It's handed a proposed answer, the positions, and it adds up those numbers once and compares with the target.
1:05Those positions are the certificate: the evidence that the answer is yes. A careful version would also reject a repeated position, or one past the end of the list, and that's quick too.
1:16At the bottom we call both. Solve on our six numbers with target nine, then verify on whatever it returns.
1:22Let's run it.
1:23We run the file with Python.
1:25The solver returned positions two and four, counting from zero. That's the four and the five, and they add up to nine.
1:31And the verifier agrees. It added those two numbers once and compared the sum with nine.
1:36So that's two different jobs: finding a subset, and checking one. Let's put them side by side.
1:43The first job is finding a subset.
1:45The solver isn't told which numbers to pick, so it works through the subsets one by one.
1:50And there can be two to the n of them, so the work grows fast as the list grows.
1:55The second job is checking a subset.
1:57The verifier is handed a certificate, the positions.
2:00It adds those numbers up once, however many there are.
2:04P and NP are, roughly, the names for these two jobs. Before we define them, we need to be precise about the question itself.
2:12Our question has one of two answers. Some subset reaches nine, or none does.
2:17A question with a yes or no answer is called a decision problem, and P and NP are classes of decision problems.
2:23We aren't asking for the subset itself, or for the best one, just whether there is one.
2:28Now the two classes.
2:30P is the class where you can find the answer with a polynomial time algorithm.
2:35Shortest path is the standard example. Is there a route from A to B costing at most five? A shortest path algorithm settles that, and its running time is polynomial.
2:45Polynomial means the running time is bounded by a fixed power of the input length. Call that length L. L squared, L cubed, any fixed power counts.
2:54And L counts the bits it takes to write the input down, including the numbers in it. That detail comes back in a later video.
3:02NP is the class where you can check an answer with a polynomial time algorithm.
3:06Whenever the answer is yes there's a certificate that shows it, like our list of positions.
3:10The certificate is polynomial in size, and checking it takes polynomial time.
3:15And when the real answer is no, every proposed certificate fails the check.
3:19Subset sum is in NP. The positions are the certificate, and verify is the check.
3:25The name NP is often misread, so let's spell it out.
3:28NP stands for nondeterministic polynomial time.
3:31The N is not for non. It's for nondeterministic, a model of computation that can guess a certificate and then check it in polynomial time.
3:39Because every yes has a certificate, you can always try every candidate and check each one. That works, and it's the brute force method.
3:48The definition only promises that the check is fast. Something much quicker than brute force might exist, and whether it always does is the next question.
3:56The question has two directions, and one is settled. Every problem in P is also in NP, because a solver can ignore the certificate and work the answer out itself. That counts as a check.
4:08The open question is the other direction. If an answer can always be checked quickly, can it always be found quickly? That's P versus NP.
4:16We don't know. The common expectation among researchers is that the answer is no, and that the two classes are different.
4:23But that's unproved. The question has been open for over fifty years, and there's a prize of a million dollars for settling it either way.
4:30Let's see what would follow if they turned out to be equal.
4:33Any answer that can be checked quickly could also be found quickly, by one general method. Hard optimization problems would get fast exact methods.
4:43And the usual encryption schemes rely on certain searches being hard. Equality would undermine that assumption.
4:49One caveat about the word polynomial.
4:51An exponent of one hundred is still a fixed power. L to the hundred is a polynomial, so an algorithm with that running time is in P by definition.
5:00So polynomial doesn't automatically mean fast enough to use. In practice the exponents tend to be small, which is why the class is useful, but the definition alone doesn't promise that.
5:11In the next video we look at how hardness moves between problems, through reductions.

Solving Versus Checking: What P and NP Mean

Created by Abhyuday DesaiPublished 3 Oct, v1Runs 5 min 21 sec

1 view

About this video

In Episode 01 of P vs NP Explained, we start with one small problem, subset sum: given six numbers and a target of nine, do some of them add up to it? A short Python program answers it two ways. One function searches through the subsets, and there can be two to the n of them. The other is handed a proposed answer and checks it in one pass. P and NP are the names for those two jobs, and the open question is whether every answer that can be checked quickly can also be found quickly.

You'll learn how to:

Tell a search from a check, and see what a certificate is: the evidence that the answer is yes
Read P and NP as classes of decision problems, the questions with a yes or no answer
Understand what polynomial time means, and that input length is counted in bits
See why the N in NP stands for nondeterministic, not for non
State the open question precisely: P is inside NP, and nobody knows whether the two are equal
See what would follow if they were equal, and why polynomial does not automatically mean practical

This video is for developers who have heard the terms and want them defined properly. No background in complexity theory is needed, and the code runs from the companion repo.

What changed

v103 Oct 2026abhydesai5 min 21 secab97bbc

First published version.

1 view0 likes on this version