Why is P vs NP Important?

In this video, I explain perhaps the most famous problem in all of Computer Science. Does P = NP? I define the terms and give examples of each. We also programmatically go through the traveling salesman problem. I experiment with a little bit of mixed reality in this video as well.

Code for this video:

Nichole's winning code:

Mick's runner-up code:

Join the Wizard's Slack Channel:

Some more great P vs NP resources:

Please subscribe! And like and comment and share. That's what keeps me going.

And please support me on Patreon!

I used the Tilt Brush mixed reality app to draw the complexity classes for fun. Thanks Az Balabanian and the Upload Collective for letting me shoot videos in VR! :
Follow me:
Signup for my newsletter for exciting updates in the field of AI:

[kevalshankershreyas]

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

[CleverProgrammer]

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

lol nice!

[rafamtz]

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!

[saurabhcarboncool]

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.

[luck]

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

[anuzis]

One of the best channels on YouTube. Thanks for the great work!

[jakewaitze]

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!

[itzmrrip]

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 :)

[jhcao]

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!

[Omcsesz]

Probably the best P=?NP video I have found yet in Youtube.

[aroncanapa]

This is my current favorite lecture on p=np

[njack]

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.

[djan]

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

[OmarMiranda]

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 :)

[oscarcastanedamunoz]

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

[huk_ger]

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

[SkullCandy]

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 !

[piponwa]

Never stop making videos Siraj! I love your channel!

[johnnywang]

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

[filipesilva]

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