P = NP Explained Visually (Big O Notation & Complexity Theory)

A visual explanation of p vs. np and the difference between polynomial vs exponential growth.
Dive deep into the enigma of complexity theory with my exploration of P vs. NP. This video delves into the fundamental principles that govern the computational universe, influenced by the brilliant minds of Von Neumann and Turing.
The origins of the universal machine and the Von Neumann architecture.
The conceptual leap from simple operations to complex algorithms.
How Von Neumann's EDVAC paved the way for modern computing.
The bottlenecks of time and space that challenge computation.
John Nash's groundbreaking perspective on computational growth.
The distinction between Polynomial (P) and Exponential (EXP) time problems.
The intriguing world of "easy to solve" vs. "hard to crack" algorithms.
The captivating realm of NP-complete problems and their significance in computing.
The 'shape of growth curve' and its impact on classifying computational problems.
Nested loops and their contribution to algorithmic complexity.
The concept of one-way functions and their critical role in computer security.
The practical implications of solving NP-complete problems.
The ongoing quest to define the boundary between P and NP.
The million-dollar question that stands at the pinnacle of computer science.
Join us on this intellectual voyage as we unravel the secrets of computational requirements, the intricacy of algorithms, and the pivotal problem that has mystified some of the greatest minds in mathematics and computer science.
Whether you're a seasoned programmer, a mathematics enthusiast, or simply curious about the inner workings of computers, this video is your gateway to understanding one of the most profound questions in computer science: Is P equal to NP?
Support new content: / artoftheproblem

[@TimBorny]

I'm still shocked at how few subscribers this channel has...truly some of the best explanations of difficult concepts I've come across.

[@ArtOfTheProblem]

@EZIO AUDITORE DA FIRENZE please consider supporting this program www.patreon.com/artoftheproblem

[@31337flamer]

this comment just made me subscribe .. 2 years in the making

[@tarisaimunodawafa3465]

Thanks, I subscribed thanks to you

[@maswinkels]

Maybe it's the irritating music.

[@azamatbagatov4933]

better than some folks in computerphile

[@albertwang5974]

So far, this is the best video on explaining P vs NP.

[@ArtOfTheProblem]

glad to hear it Albert -thanks

[@steezyboi96]

this video is better than the p vs np video with 1.4 million views. great job!

[@ArtOfTheProblem]

Thank you for the feedback. KZbin's algorithms are not biased towards this channel since I've slowed content production

[@linly.]

Watched quite a few videos on this as I kept scratching my head when trying to understand my professor's way of explaining it. I have to say this video really made it click. Definitely so far the best one I've seen on KZbin. Writing a comment to show my support and gratitude!!!

[@ArtOfTheProblem]

thank you! i know your pain and glad this finally helped

[@randyzeitman1354]

I have seen over a dozen P versus NP videos and this is far and away the clearest… Veritassium level clarity video.

[@ArtOfTheProblem]

appreciate it

[@SiddharthPrabhu1983]

By far the best explanation of P vs. NP on KZbin. The background on complexity theory was great to contextualise exactly what it means to define a computing problem as easy or hard. Fantastic work!

[@ArtOfTheProblem]

I really appreciate the feedback Siddharth, I watched every video on KZbin and then made this one to correct the confusions. Stick around more to come

[@SiddharthPrabhu1983]

Looking forward to it. You've got yourself another subscriber.

[@UnPuntoCircular]

Your videos are amazing. Really well presented as always. I'm not sure if this is due to my increasing interest in Computer Science alone, or the fact that you teach it carefully by building each step in a logical, reasonable and motivated way. I admire that way a lot! Thanks for sharing and keep them coming!

[@bakedutah8411]

UnPuntoCircular, it’s their careful teaching (although, no doubt your increasing interest in CompSci helps!). I have a CompSci PhD, and although it’s not in complexity, I’ve read through P vs NP stuff umpteen times, including the excellent Gary & Johnson, and this is all familiar and friendly territory for me. That all said, this little video blows the rest away for getting exactly the right points, of exactly the right priority in terms of understanding, in exactly the right order. G & J, and the rest, are where to go next to start putting details into this skeleton, but it is by far the best skeleton I’ve encountered.

[@JawnLam]

I've been following your channel for a while and love every video! Keep up the great work! This is one of the best explanations of PvsNP I've seen. 👏🙌👏👊

[@CrucialMuzic]

I miss your videos , glad to see one today!! Very informative as usual! Thank you :)

[@miuixtli]

This is, hands down, the most beautiful and clear video on this topic I've watched.

[@ArtOfTheProblem]

wonderful to hear I appreciate the feedback, please stick around

[@dangerlibya2010]

I've been waiting for this a long time, thanks a bunch! I love how you stay loyal to your channel's name; you always make the viewer live the problem before introducing the solution

[@Aage152]

This is the best definition I have heard - until now, of this problem. Thankyou for sharing.

[@vincelaszloszalma2103]

I'm working on a complex problem. I was stuck in the process. I'm beyond the second minor nervous breakdown during the day. Then I found your video. With a single analogy you mentioned, I was able to move on with my research. Sir, I find your channel invaluable, and I honestly appreciate your method of presentation. Thank you!

[@ArtOfTheProblem]

wonderful! I made this video out of the stress I felt when first confronting the topic.

[@tauxca]

Thankyou for the simplest explanation for a complex theme, you are really helping a lot of people. I believe whe you say it was a hard work, congrats and blessings!

[@justme-hh4vp]

I've watched a lot of P vs NP videos and this one helps resolve virtually all the questions I had and some i didn't realise I had. It is the only video i've seen that makes a good connection Exp and P and then defines NP and NP-complete. It is much clearer this way. The looping explanation also helps connect it with other explanations i've seen about Goedels incompleteness theorems. Background music a bit annoying but otherwise excellent.

[@nidhirathi11]

You guys are great! Well written and directed videos.

[@gb213]

Thank you for this gem of a video, I've watch dozens of videos and read many articles delineating these concepts but you have done it in a very robust and lucid manner that I feel like I have a good idea of what these concepts entail. Hats off to you!

[@ArtOfTheProblem]

thank you, i made this video for this exact reason

[@kmunson007]

I couldn't hit that subscribe button fast enough!!! Fantastic explanation. And the background music made me chuckle - like something from a Twilight Zone episode that got more bizarre as the video went on. I can't wait to plow through the other videos on your channel.

[@ArtOfTheProblem]

Welcome to the party! glad you found us, i actually do have a new video comng soon

[@Samucacamilo]

What an amazing video! I learned more watching this video than in my whole NP completeness class!

[@ArtOfTheProblem]

thrilled to hear this. my motivation for this channel was how I felt in those classes! it didn't need to be torture but for some reason the professors take comfort it making it hard

[@odinakazeus]

Thank you for this video. I saw others and they failed to properly explain what the P vs NP thing was and it just became frustrating. Keep up the good work!

[@ArtOfTheProblem]

excellent, that was the hope here, to address that gap which existed in my mind - I know the frustration you felt

[@ozzyfromspace]

You're freaking amazing, man! You compiled the P vs NP problem into a simple form that I can understand with almost no math. I'm really impressed!

[@ArtOfTheProblem]

thank you kindly, I worked really hard on this video and I'm glad people are finding it.

[@ozzyfromspace]

@@ArtOfTheProblem "*I worked really hard on this video*" Trust me, everyone can tell. I've watched some really bad P vs NP videos, so to go from that to content this good is a major leap. Again, thank you!

[@myronwoods40]

I have read and watched tons of material on this subject and this is hands down the simplest and clearest explanation of this problem

[@ArtOfTheProblem]

thrilled to hear it. I tried to read everything out there and I was striving for something much better to help people out

[@shelockguan9060]

best ever!!! better than any university! very creative you have the talent of being a director, sensitive,logic, good-story teller ,knowledgeable and romantic

[@vincentlemoine3830]

Thank you for this video, before it I just couldn't understand why P=NP was something worth a million dollars, now it make sense because it would save a lot of money.

[@ArtOfTheProblem]

awesome glad this helped

[@punditgi]

Best explanation of this topic I have ever come across. Brilliant!

[@ArtOfTheProblem]

glad it helped :)

[@yomanos]

This channel is very well made, keep it up!

[@robertbohrer7501]

Also the best P vs NP explanation I've ever seen. Your channel will explode in popularity, just give it time.

[@badrbellaj1212]

the quality of this video means you undertand well what are you talking about. I've enjoyed it, big thanks.

[@redapplefour6223]

excellent description, been recommended a lot of millenium prize problem videos on youtube lately for some reason and this one's quite well put together

[@ArtOfTheProblem]

appreciate the feedback

[@EdissonReinozo]

This is the beat N vs NP explanation I have watch. Thanks

[@Eta_Carinae__]

Welp, I did it. The historical approach is always pretty great. It's great for being able to follow the chain of thought in each idea. Cheers for the content!

[@ArtOfTheProblem]

awesome that was the idea behind this channel, following a conceptual progression through time.

[@rvikwd]

This is extremely well done, excellent video! Thanks for helping me finally understand this! ♥️

[@ArtOfTheProblem]

Thanks for the feedback, really proud of this video

[@prorigami2444]

Possibly the best video on the topic. Thank you!

[@ArtOfTheProblem]

new vid! kzbin.info/www/bejne/hXe2amNje71ppsk

[@jng9324]

This is pure gold, by far the best explanation of P vs NP that I came across.

[@ArtOfTheProblem]

glad you found it

[@ItachiUchiha-ub2iu]

Brilliant explanation, this channel is goldmine!

[@ArtOfTheProblem]

So happy you have found this channel stay tuned for more!

[@robocop30301]

This is a really great video. Such a great explanation.

[@rongxinzhu]

You are conveying the hard concepts amazingly well.

[@ArtOfTheProblem]

appreciate the support, please stick around!

[@cubostar]

This video is incredible. The explanations are so concise and easy to understand despite being difficult to look at initially. Thank you so much for this resource, it's truly a gem of education.

[@ArtOfTheProblem]

thanks for your feedback it means a lot to me. I spent a long time trying to get this one right

[@cubostar]

@@ArtOfTheProblem No problem! Computational theory has always been interesting to me, but it was too intimidating to learn when trying to read Wikipedia pages that explained things in incomprehensible jargon. The beauty of this video and why it stands out from similar videos is that it explains the jargon as well, letting viewers be able to communicate with other people and not just understand the concept in layman's terms.

[@ArtOfTheProblem]

@@cubostar awesome, that's always been the goal

[@hemanthkumar240]

The best detailed explanation of most toughest topics like COA etc . Thankyou so much sir ❤️🙏🙏

[@thickthies5000]

This explanation is fantastic. It is extremely easy to understand and the hand drawn visuals made it even more stimulating. Thanks so much, you have a new subscriber!!

[@ArtOfTheProblem]

wooo, awesome thanks for the feedback!

[@jdi378hns]

first video ive seen that explained the p vs np thing in a way i could understand. thanks!

[@ArtOfTheProblem]

happy you found this, stay tuned!

[@valentinsenicourt8608]

Thank you for this video, it was very interesting. I work in parallel computing and science, but did not receive a formal computer-science education. It was well-executed

[@Madsy9]

Great video on complexity theory. The only thing I wish you had covered is how the NP-complete class is defined by the Cook-Levin theorem and boolean satisfiablility.

[@StefanTheFink]

Very well done, not only this video but the whole channel! Keep it up 👏

[@ArtOfTheProblem]

Thanks Stefan, I'm really happy with this CS series. Currently trying to develop a similar one on AI

[@StefanTheFink]

@@ArtOfTheProblem I'm surely looking forward to that! The topic of AI is as popular as it's complicated, but you definitely have both knowledge and talent to develop it well 😊

[@Simppi96]

Well done, good sir! By far the easiest to follow explanation of P and NP I have found on the web so far =)

[@ArtOfTheProblem]

Thank you, put a lot of work into this and happy it's finally helping people.

[@arastooajorian9069]

That was amazing. It was one of the best scientific explanations of a hard concept in a very clear method and easy to understand.

[@ArtOfTheProblem]

awesome, glad you still found this

[@irisyazc739]

Thank you so much for the great explanation and visuals!

[@ArtOfTheProblem]

thanks for feedback

[@mani1672]

I am being honest when I say this..... This is the best explanation to this problem that I have found online. Love the explanation !!! Thanks for putting the time into making this !!

[@ArtOfTheProblem]

I appreciate the kind words. I know you are being honest because before I made this video I watched everything and was disappointed

[@deslomator]

The best P vs NP explanation I've seen

[@ArtOfTheProblem]

thank you, I struggled with this one

[@shandou5276]

This is the best-explained video about polynomial time that I have ever seen! Amazing work!

[@ArtOfTheProblem]

thrilled to hear this. i worked really hard on this video and i'm glad people are still finding it

[@shandou5276]

@@ArtOfTheProblem it is illuminating work like this that bits by bits lift all of us up. I am feeling lucky to have run across it. Will explore more in your channel and hope you keep up the great effort!

[@ArtOfTheProblem]

@@shandou5276 wonderful :))) please do. i have more on the way

[@gemechumekonnen8786]

I've watched a few np vs p videos. this has been the clearest. Thanks!

[@ArtOfTheProblem]

super glad you found it

[@diegobytesback]

Extremely well explained, wonderful video! Keep em up :)

[@ArtOfTheProblem]

thank you, glad you found it

[@ekathe85]

This is such a good explanation to such a complex concept, that I'm seriously questioning whether or not I understood it.

[@ArtOfTheProblem]

couldn't ask for a better comment

[@CaptainSlowbeard]

Thank you! This should be the standard video people point to as a clear explanation of P vs NP - this also was the first time that I think its clicked for me what is really meant by polynomial and exponential time, cheers!

[@ArtOfTheProblem]

fantastic glad to hear it. That was the goal of this video as I never found the existing ones satisfying

[@dekippiesip]

@@ArtOfTheProblem Just one more question, when you talked about the 'non deterministic' machine I thought you where alluding to the quantum computer. A lot of the NP problems van actually be solved in polynomial time by a quantum computer(like breaking down a number into primes), do you think quantum computers could solve all NP problems in P time?

[@dekippiesip]

That is the problem I have with explanations that try to dumb things down too much. The result is that it actually becomes harder than just explaining it properly with the maths involved. Their vague discription just tells you that P problems can be solved 'fast' and 'E' problems can't. And that's it.

[@QuanNguyen-og6pq]

The best explanation on this topic!

[@m.a.g.r1858]

I think I was hypnotised by this video and it was beautifully explained. Thank you so much! Answered so many related questions I had

[@ArtOfTheProblem]

wonderful...thank you

[@mksarav75]

It is one of the best explanation of P Vs NP. Thank you so much for explaining it in such simple way.

[@ArtOfTheProblem]

please share thank you kindly

[@moart87]

My god, this is by far the best explanation of this topic.

[@marcwolf2254]

I have watched so many videos on this topic and was like a deer in a headlight. You sir made it totally relatable.... Thank you!!!

[@ArtOfTheProblem]

SWEET! that was my goal, thrilled to hear it.

[@alanhamilton2619]

What a fabulous video. Thanks!

[@annonymousfox7515]

Okay, I liked this video so much I logged in on a library computer just to like and subscribe! AMAZING explanation!

[@ArtOfTheProblem]

awesome I'm thrilled this video is helping others find their way. appreciate it

[@TheCCBoi]

Amazing video, helped me with understanding my course materials.

[@ArtOfTheProblem]

thanks glad to hear

[@xruan6582]

straightforward and easy to understand, and most importantly, presented in decent speed.

[@ArtOfTheProblem]

appreciate the feedback

[@diego898]

Welcome back!

[@by2154]

Chapeau. Perfect, simple explaination

[@ArtOfTheProblem]

thanks for the feedback glad it helped

[@tanvirhasanmonir1627]

Wow! What an amazing explanation he provided!

[@ArtOfTheProblem]

appreciate your feedback

[@petertailor8545]

Best explanation ever!!!!!!

[@GideonMaina]

Kudos , helped me finally understand P vs NP esp the non deterministic computer part

[@ArtOfTheProblem]

great to hear

[@brendawilliams8062]

A nice informative video. Thx

[@edlodude]

Man I wish I found this video last semester

[@lerneninverschiedenenforme7513]

This is the most best best best most best explanation I've heard so far regarding complexity and p np. Unfortunately numberphiles/computerphile's videos appear much earlier in the result list of utube :(

[@ArtOfTheProblem]

Thanks for the feedback, I worked really hard on this one.

[@kaitlyn__L]

this video made me learn i was completely misunderstanding the categorisation, like i thought that P=NP meant we just need to find the right hardware, rather than it also inherently meaning the existing type of computer. i also didn't realise that NP was distinct from EXP problems, until this video. all of your channel's videos have really good explanations and i too wish they showed up higher in results lists. many mathematical ideas i had been able to use perfectly competently for years, i never really got what they "were", until these videos. so thank you!

[@ArtOfTheProblem]

Thanks so much for your feedback (NP problems are EXP problems we can verify quickly). Thrilled to hear people are gradually finding this video.

[@Alice_Walker]

Thank you very much. I'm reading Ian Mcewan's "Machine's Like Me" and this really helped me better understand a couple of important things the main character talks about 🧠✨

[@ArtOfTheProblem]

so happy it's helping people

[@Belishop]

Well explained, thanks.

[@user-mm2hn3ju4u]

Best explanation on youtube

[@ArtOfTheProblem]

glad you found this

[@emiliozorrilla5188]

excellent as always, thanks!

[@TheRealBuckNorris]

That was very clear! Thanks!

[@bluestacksummer6755]

thank you very much for your effort

[@hp-qx7tf]

Thank you for this video.

[@pierreschweitz-navio3831]

Great video !

[@avocat215]

A brilliant explanation

[@ArtOfTheProblem]

glad you enjoyed

[@sabahhadhood603]

excellent lecture

[@JeffreyAborot]

Wonderful presentation on the topic! In contrast to the usually very dry presentation in class.

[@ArtOfTheProblem]

thank you, yes I know how horribly try this class can be

[@wennie2939]

Best ever!

[@beckycheng9292]

Videos contain a lot of interesting and helpful information, but I must say, the music makes me feel tense.

[@robertdtodd]

So well done

[@ArtOfTheProblem]

appreciate it

[@spqri3]

Many thanks. Make my brain understand. Wow.

[@ArtOfTheProblem]

thrilled to hear it

[@josephmarshall2030]

Thank you!!! Like henry jacobowitz,brieske(author of world book enclopedia math stuff) & kinertia you are a master teacher!!!! 🥰🤩😁

[@IITeens]

loved the video a lot ❤❤❤❤❤

[@ArtOfTheProblem]

stay tuned

[@lukeyd13]

Beautiful stuff

[@ArtOfTheProblem]

thank you luke

[@joshuaclancy8093]

I watch education videos all the time, for years, and I just found this channel... well the youtube algorithm sucks, but holy hell this channel is good. binge time!

[@ArtOfTheProblem]

thrilled to hear it! the algorithm hates this channel I agree it sucks

[@tdvwx7400]

Amazing video, thank you!

[@ArtOfTheProblem]

appreciate the feedback!

[@tdvwx7400]

@@ArtOfTheProblem I was struggling with this concept for quite some time, but this was a great explanation. Keep up the good work!

[@sipanmohammed]

Great video, thank you

[@techfunwithaadil]

Thank you sir ❤

[@ArtOfTheProblem]

thank you, loved making this one

[@alexyangfox]

Really great !

[@ArtOfTheProblem]

glad you found this

[@MagicEel2024]

Amazing, this video touched perfectly on the contents of the Open university syllabus and expressed most of the key points! Thanks! How is it some of you content creators are able to simplify 2 months of study with a university into 11minutes? These NP problems in my mind suddenly all became P! 👍👍👍😁😁

[@ArtOfTheProblem]

so happy to hear it, I spent easily over 2 months thinking about how to compress it like this. I also suffered through the courses where I felt lost for a year :)

[@jishnuchandran283]

Thank you so much sir!

[@ArtOfTheProblem]

glad you found this video, i love this one

[@sunphilkwon7545]

Hi! can you make another video about NP Hard? your video made me understand this concept more than any other material

[@dozydanny4927]

Great video! But why is the music so scary

[@adammikoajczak306]

Great video. What about NP-hard problems?

[@tylerduell1761]

Why do I even go to college bruh this is better than anything I’ve ever heard from a professor

[@ArtOfTheProblem]

Thanks Tyler, my frustration with how professors covered this lead to this channel and videos like this. down with the institutions!