Why is P vs NP Important? 

Fun Fact : Unfortunately proving is an NP problem,so the P vs NP problem itself is an NP problem.

1:05 "1 + 1 = 3 if you don't use a condom". lol nice!

I think I'm having a huge bromance. High quality videos, amazing sense of humor and deep knowledge about advanced topics on Python. What else could any programmer ask for? Seriously, thanks for everything man, keep up the good work!

You make problems simpler which I use to think complicated. If you keep doing this thing People teaching people. The world will a whole new place.

One of the best channels on RU-vid. Thanks for the great work!

Let N = 1: => P = NP QED

I have discovered a truly marvelous proof of this, which this comment box is too narrow to contain.

This was a fantastic video! Watched a few others on NP complete and was not able to grasp what it is until I came here. Thank you!

Thanks for making this. I noticed a number of the other commenters don't see how if P=NP, things in the world would change. Using the math behind RSA (and its trapdoor function) is a good exercise for explaining why this matters, since asymmetric encryption algorithms based on trapdoor functions are used in all of our secure communications. Thanks again! Also, not sure how new the slack chat is, but I am definitely joining. Wish I knew about it earlier!

Probably the best P=?NP video I have found yet in RU-vid.

This is my current favorite lecture on p=np

Just a million bucks for creating billions and billions of wealth??

if I hadn't read a magazine article on this, I would be lost listening here ..comparing n to the x power with x to the n power, helped me to see the nature of growth in complexity

Do not know how to code but for traveling salesmen problem just break down the map into a grid and determine the shortest way out of individual squares in any direction. With squares with destination in them it would shortest with that intersection. From there you move the grid with overlap of the previous squares until a route is shown in a loop.

the only way to make P=NP is to eliminate the concept of time we used to think in 3D. So, 4D P may equal to NP.

sweet jeebus. this channel is tickling me in just the right way. i like your energy! and the fact that compsci is the main topic of your channel makes me nerdgasm. i wish more channels were like yours, haha. subscribed :)

Never stop making videos Siraj! I love your channel!

Hey Siraj, thanks so much for so many awesome videos!

This is the best explanation of P & NP I've seen

Really well done! Also good to see your channel growing, keep it up :) Cheers from Germany

love this series idea-- would love for u to keep going with this

Awesome video Siraj! When you tried to compute the TSP using teapot (genetic algorithm) my mind explodes, because that was just an intelligent backtracking (and very hard way to solve an NP problem) and it wasn't much related to deep learning (sorry, my CS background was very hard theoretical :( ) as it first came to my mind. And now that you explain again the TSP, using it to explain the real issue associated with it (NP) it makes more sense jajaja :) gonna try to upload a convex hull heuristical approach to solve TSP ;) btw, love the VR explanation :)

This channel is so good. Thanks Siraj for making these videos!

Hint: it involves a graph, a hash map, a priority queue and an algorithm developed by dijkstra

Proving P=NP, considered quite unlikely, wouldn't necessarily provide a feasible solution to NP-complete problems. The degree of the polynomial could be something monstrous like 10^10, or 10^1000, or worse.

Excellent video Siraj! That VR drawing looks like fun. What do you think of the Shor Algorithm which enables quantum computers to solve the NP-problem of prime factoring in polynomial time.

siraj u rock !! u have no idea how much ur videos helps the beginners.. awesome video on using ML libraries to use..! plz can u suggest more on which couses and materials to go for.. what are the fields in data science .. also a video on deep learning would be awesome..

P = NP if N equals 1 :) Give me my money. Check out "Quantum computing since Democritus" by S. Aaronson if you have time, it's an awesome book. Great video as always !

So, as far as see, P subset NP, and for some n (number of problems) belongs to NP, NP = P, I mean that some of problems that classified as NP are also classified as P... So the question is to prove it for all n? One more thing to make sure i understand regarding the NP Hard: is it for infinite calculations ? (e.g. calculating all possible numbers in the world)! Please confirm my thoughts if wrong or right...

What an excellent explanation. Also, praise be to Slimeman.

I don't really understand why P=NP would necessarily mean there is one algorithm that can solve all problems. Could anyone explain? Nice video though!

Loving this channel man, great content, keep it up!

Loved the woman playing catch with her dog in the background nice contrast to the video

So basically if p=np a computer would already have to know a way of figuring something out before we even know that we need to figure it out, it’s pretty simple but the question literally is itself making it a pretty big massive loop so no matter what at some point we are going to find something we don’t understand

P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed. I show a solution to that problem as follows: Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP. You could read the details in the link below… hal.archives-ouvertes.fr/hal-01509423/document

So what is the formal, quantifiable definition for NP-Hard? I read on Wikipedia that the qualification for it is "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H, that is: assuming a solution for H takes 1 unit time, we can use H‎'s solution to solve L in polynomial time." Am I misunderstanding this or does this mean that to qualify for NP-Hard the solution must be able to be reduced to solve any NP problem?

life saver....this is the video that will help me solve my discrete math assignment

Hi Siraj. Im really enjoying your machine learning videos on your channel. I have a question. If 1 were to make a 2048 ai, how would 1 go about implementing a neural network in the ai.

btw it's longest common subsequence. the longs common subset would just be union which you can do in linear time depending on how you specify the basic operation.

Hey Siraj, could you please do a video on reinforcement learning for control in continuous action space (i.e. quad copter landing, cart pole, double pendulum, etc.)?

Hi Siraj!! Great video as always. My friends and I just discussed a lot about Complexity theory on our group study, you're one day late lol, jk. We talked about it in a more formal way using DFA/NFA and such.. Would you be kind to make an awesome video about Bayesian Nets or something similar? :D

This is the most amazing explanation i have ever seen

This was amazingly interesting and very well explained! Love it

what about this problem - for some table of data, where the first column is a list of unique nominal categories, and all other columns are various metrics associated with the category, is there a way to find the linear combination (or any other combination) of metrics which, when sorted, results in a pre-specified order of the unique categories? For example, I have some data where the first column is a list of fruits, whereby there is only one row per fruit. Each additional column represents some normalised nutritional property of that fruit (so an Orange might have the value 1 for vitamin C as it is the highest relative to the other fruits). If I specify a ranked preference of fruit (1 Apple, 2 Orange, 3 Banana), is there a way I could find which 3 nutritional properties when averaged result in that rank or a rank that most closely resembles the specified one?

Hey! Just wondering do you happen to have any resources to recommend to start learning about computer science? Perhaps a Computer Science for Dummies book? :P

You are cool. A ginormous like (y). I was getting sucked into laziness but you my friend pulled me back. Thanks bruh.

The third assertion: "If P=NP, we could solve any problem fast" is not accurate. Problems that are ExpTime-complete cannot be solved in polynomial time.

I like your channel already open source and lots of energy

Best video about the P vs NP in simplest way :P

This video is awesome but I got a bit confused: As far as I know, the Halting Problem is not NP-Hard, it's actually undecidable, isn't it? Or I am mistaken? Thanks for the amazing video :)

PLEASE you have to tell me where you're getting these pictures

Just curious, Where was this video recorded? It looks like Northern California.

There is a movie about this problem called Traveling Salesman. Pretty trippy

meta-heuristic methods as you mentioned, like genetics algorithm are the best way, some other meta-heuristics are particle swarm, ant colony and ....

Siraj, thank you for your video. However the claim at ~5mins about the longest common subset being an NP problem is not correct, this is solved in polynomial time (n^2) using dynamic programming. Look up "longest common sub-sequence". Perhaps you were trying to define another problem?

could the quantum computing help with this problem? find optimal answer from big set of information.

I dont have sound right now so no clue what you're saying but from the little pictures in the top right, cool video!

0:34 "Poynomial"... Typo.

it's not a correct statement what was said at 1:45-1:50 = "we have to try every single solution to find the best one"... Then basically it is a counting down algorithm to construct each solution, which is NOT an algorithm for a specific problem. The idea is that you exploit the problem "structure", how you construct the solution so you find better and better solutions jumping over solutions which are worse then what the alg has found. Then this "jump over" is the essence of the alg. So the idea is that there is an abstract algorithm (solving a problem) to which an instance of the problem's date (e.g. 45 specified US city in Utah, or 156 US cities in california for the TSP) is given and then the size (maybe several metric for the size) is a variable (or may variables, like # of clients and # of warehouses in a product delivery planning problem) in an expression, which gives the "time" (there might be ticks/moves/etc for measure not just time) to arrive to the best solution. In NP problems the existing algorithms so far are NOT polinomial, but exponential. Also there are many measurements for this "time" thing like average, worst-case, etc by which the algorithm is measured. In addition, though theoretically indeed a polinimal alg is a good stuff, for large instances it can still "blow up" (= takes too much time to compute)... so even if a polinomial alg has been found for a problem still everybody tries to find something which is some "log n" type, where n is the "size" of the problem...

I now understand this problem, thank you!

Was half expecting an Indian accent. Thank you for this!

thank you, I understand knapsack as well because of this video!!!!

absolutely love this channel

Love your stuff!

I'll add two examples if anyone's interested. First, here's a *failed* attempt at P=NP; Take a problem instance of the circuit value problem (a random, 'P-Hard' circuit), and transform it into an instance of Horn Satisfiability. Now drop the inputs. The remaining object is a representation of the satisfiability of a general polynomial time circuit. Circuit-SAT is known to be NP-complete, however this approach fails (Hint: dual rail logic). Second, here's an ongoing attempt at L≠NP: With SAT briefly described above, show that an L-complete satisfiability problem (such as exclusive-or 2-SAT) represents a functionally incomplete set of circuits (Maybe it does, maybe it doesn't).

you drew the complexity classes in tilt brush ... *claps*

I like your programming videos because these cool ML applications and stuff are totally gonna make more people get into CS. However, when it comes to theory, it is very, very crucial that you are exact and make as little errors as possible. This video contains quite a lot significant errors tho! NP-hardness has nothing to do with whether a problem's solution can be verified in polynomial time or not. When a problem is NP-hard, any problem that is in NP (as you mentioned, that means a problem's solution can be verified in polynomial time) can be reduced to the problem that is NP hard. The halting problem is NOT NP hard, it is instead undecidable! Decidability isn't even about computational complexity. These concepts are related because they are both based on Turing machines, but they are not the same at all. An NP-complete problem is one that is in NP and NP-hard. Hence, if you can solve an NP-complete problem in polynomial time, because you can reduce any other problem in NP to it, you can solve any problem in NP in polynomial time. This would mean NP = P. Finally, as you mentioned, there indeed are problems that are (probably) even harder to solve than those in NP (e.g. problems in NEXPTIME). But that also means that P = NP does NOT imply that any problem can be solved in polynomial time, as you falsely claim. Please clear these things up, be more careful next time and keep up the great work

I'm not quite sure that you got all the facts right. First of all halting problem is undecidable but when we're talking about complexity, we mostly stick to the decidable problems. I guess halting is polynomial-time Karp reducible to any decidable language (haven't checked it for real though), but giving an unsolvable problem as NP-hard is kinda not nice. There exists problems that is believed to be harder than NP-complete problems. Another bothering wrong point mentioned in this video is that there are no problems (decidable problems) that are harder than NP problems. Well we haven't proved there are harder problems than P problems (:D) but there exists class of problems believed to be harder than NP. Just take a look at polynomial hierarchy or EXP (for love of complexity!!). You mentioned math at some point in this video. Well math was complicated before computation was discovered. In fact Gödel proved there are statements (in any non trivial formal system) that cannot be proved or disproved in that system. So math is already complicated. The only connection between P vs NP and mathematical proofs is noted by Gödel himself in an interesting letter to John von Neumann. It is now known that proving a statement in a formal system is NP-complete. Intuitively we know finding a proof for a theorem is much harder than merely verifying one. So in our guts we do believe than P is not equal to NP (sorry man). So in no way proving P not equal NP would mean there are no problems than can not be solved, as it is already proven that those problems exist. An example would be continuum hypothesis. If you're interested in what happens if P vs NP gets solved (in either way) you can study Impagliazzo's Five Worlds. Best wishes, Someone who cares about Complexity Theory :)

Does extrapolation not answer temp in future with data?

what if we use DQN and traverse through the state space tree (solution tree). It wouldn't consider all possible nodes and quickly traverse to the leaf node. Thus TSP problem would be solved in polynomial time. what do you think?

how about solving for the smallest area. plot all the cities as perimeter points and solve for the smallest area.

Dude! Your vids are awesome. Can you make a vid on XGBoost?

Really good video!

AND I HAD SEEN ALSO THE THEORY OF PREDICTION EVENT ON THESE MOVING WHEN CALCULATING FACTOR, IT IS A KIND OF COMPUTION JUST WITH THE NUMBER OF ELEMENT , SO POLYNOMIAL IS BUT IS NOT CONSIDERED BECAUSE YOU CAN PREDICATE WITH KIND OF METHOD

So what if we find out P does equal NP but we cant figure out the algorith that allows that to happen? Does that mean P does not equal NP?

refreshing video. cheers man!

You gave me a massive headache but it was so worth it :D

what is the name of the device that you are using to write? at 4:35

why this video was not made when I took the algorithm class...

I had to replay the video. You distracted me with the 1+1=3 Without the Condom meme.

6:42 Rigby: richard is a good guy but, you know...

how have we gone to the moon using a million lines if code and Primitive Technology, but cannot solve an A to B to C to ect..back to A?

I SWEAR I HAD MANAGED TO SHOW THAT P=NP ; BUT AT THE TIME THE FIRST APPLICATION WAS MUSIC .AND I DIDN T SEE HOW TO GET THE APPLICATION ON FACTORING , I HAD SEEN ON MY EQUATION THAT A KIND OF THEORY OF NUMBER HAS APPEARED , BUT NO FACTORING AT THE TIME ... NOW ,SINCE JANUARY 24TH 2017 I HAD TAKEN BACK THE CALCULATION AND I HAD FOUND THE IMPORTANT PART OF P=NP , IT IS THE NUMBER THEORY WICH LEAD TO FACTORING . NOW I HAD SEEN LOTS OF APPLICATION MENTIONNED ON OTHER VIDEO OF P=NP ON THI APPLICATION OF P=NP ON FACTORING , I HAD SEEN RUBBIX CUB MOVING SALESMAN MOVING ,COMBINATION MOVING , AND DUPLICATION MOVING AND QUATUM MOVING , AND OTHER ....I SWEAR I CAN FACTOR A NUMBER OF 800 DECIMAL DIGIT , WITH HAND ,AND JUST FOR 5 HOURS , WHEREAS WITH A 3Mhz COMPUTER THIS WILL BE DONE LESS THAN 2 MINUTES

p = np is already a np problem. So does it mean that if nobody solves this, than np does not = p? Then p = np problem would be solved by itself..

What math courses did you take at College?

what I don't understand is why all NP problems are treated as the same. E.g. let's say I have a problem, and the current algorithm for solving it runs in exponential time. Then someone figures out a better algorithm to solve it in P time. How does this help solve other NP hard problems? Let's say I'm really bad at writing algorithms for some known P problem and i write a NP algorithm. Then someone corrects me and shows me a known P solution. How does this (already existing) solution help solve current (unsolved for now) NP problems?

I have a marvelous proof for P vs. NP, but ... Oh, sorry wrong question.

Anyone knows a list of problems (like top 10,20,50,...) and the current estimated value in $ for the solution?

Okay, I gotta ask. What was that blue sorcery?!

I can say things all the time but will I evere get it right

wouldn't the call stack run out of memory?

I thought you were talking about myers briggs P vs NP lol I am an ENTP

So if the solution already exists or can be somehow provided for you and can be examined, verified and validated then it doesn’t need to be created by any sort of brute force method or built from scratch. This sounds like the chicken or egg/which came first conundrum to me. Problems like this appear to be unsolvable because of the lack of a higher perspective. If one is inside of a box and unaware that there even is a box, meaning that they believe that everything inside the box is all that is, it would never occur to them that there is an outside (of the box). In that mindset they’re not considering everything, even though they think they are because their concept of everything is limited when in fact “everything” implies the infinite and infinity as a concept has no borders, limits or even rationality. My brain hurts.

Sir , can you please tell me how to take advertisements on website? I tried to Google adds but unable to do that they rejected my application. I had developed more then 10 website now thinking of making some money out of them. please help me.

Did human solve all kind of its own problems so far ? Maybe evolved machine can solve hard-NP in a sec or halting problem ;D

You are awesome dude!!!!!!

This is so dumb I feel dumb thank you for broadening my scope

I expected this video after my comment on your previous video for some reason.

I doubt they are equal, we already know how to solve NP problems, it's in the name, non-deterministic polynomial time. That's what makes me think they aren't equal, they are equal if we could make a deterministic machine to work just as well as a non-deterministic one, which clearly isn't the case.

P cant mean np, it would be like saying that if you know to solve something little, you are perfectly good at it (hard to explain)