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
Пікірлер: 341
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
4 жыл бұрын
@EZIO AUDITORE DA FIRENZE please consider supporting this program www.patreon.com/artoftheproblem
@31337flamer
4 жыл бұрын
this comment just made me subscribe .. 2 years in the making
@tarisaimunodawafa3465
4 жыл бұрын
Thanks, I subscribed thanks to you
@maswinkels
3 жыл бұрын
Maybe it's the irritating music.
@azamatbagatov4933
2 жыл бұрын
better than some folks in computerphile
So far, this is the best video on explaining P vs NP.
@ArtOfTheProblem
5 жыл бұрын
glad to hear it Albert -thanks
this video is better than the p vs np video with 1.4 million views. great job!
@ArtOfTheProblem
6 жыл бұрын
Thank you for the feedback. KZread's algorithms are not biased towards this channel since I've slowed content production
Precisely explained video within 11 minutes,Thanks to the all the person's involved in the video..Gr8 research work...🙌
@ArtOfTheProblem
13 күн бұрын
thanks glad people still find this
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 KZread. Writing a comment to show my support and gratitude!!!
@ArtOfTheProblem
3 ай бұрын
thank you! i know your pain and glad this finally helped
I have seen over a dozen P versus NP videos and this is far and away the clearest… Veritassium level clarity video.
@ArtOfTheProblem
10 ай бұрын
appreciate it
By far the best explanation of P vs. NP on KZread. 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
4 жыл бұрын
I really appreciate the feedback Siddharth, I watched every video on KZread and then made this one to correct the confusions. Stick around more to come
@SiddharthPrabhu1983
4 жыл бұрын
Looking forward to it. You've got yourself another subscriber.
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
5 жыл бұрын
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.
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
4 жыл бұрын
wonderful! I made this video out of the stress I felt when first confronting the topic.
This is, hands down, the most beautiful and clear video on this topic I've watched.
@ArtOfTheProblem
4 жыл бұрын
wonderful to hear I appreciate the feedback, please stick around
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. 👏🙌👏👊
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
4 ай бұрын
awesome glad this helped
I miss your videos , glad to see one today!! Very informative as usual! Thank you :)
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
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
5 жыл бұрын
thank you kindly, I worked really hard on this video and I'm glad people are finding it.
@ozzyfromspace
5 жыл бұрын
@@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!
This is the best definition I have heard - until now, of this problem. Thankyou for sharing.
What an amazing video! I learned more watching this video than in my whole NP completeness class!
@ArtOfTheProblem
4 жыл бұрын
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
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
4 жыл бұрын
thanks for your feedback it means a lot to me. I spent a long time trying to get this one right
@cubostar
4 жыл бұрын
@@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
4 жыл бұрын
@@cubostar awesome, that's always been the goal
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.
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
6 жыл бұрын
excellent, that was the hope here, to address that gap which existed in my mind - I know the frustration you felt
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!
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
4 жыл бұрын
thrilled to hear it. I tried to read everything out there and I was striving for something much better to help people out
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
6 жыл бұрын
fantastic glad to hear it. That was the goal of this video as I never found the existing ones satisfying
@dekippiesip
4 жыл бұрын
@@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
4 жыл бұрын
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.
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
11 ай бұрын
Welcome to the party! glad you found us, i actually do have a new video comng soon
Also the best P vs NP explanation I've ever seen. Your channel will explode in popularity, just give it time.
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
3 жыл бұрын
thank you, i made this video for this exact reason
best ever!!! better than any university! very creative you have the talent of being a director, sensitive,logic, good-story teller ,knowledgeable and romantic
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
5 жыл бұрын
awesome that was the idea behind this channel, following a conceptual progression through time.
You guys are great! Well written and directed videos.
This is such a good explanation to such a complex concept, that I'm seriously questioning whether or not I understood it.
@ArtOfTheProblem
5 жыл бұрын
couldn't ask for a better comment
first video ive seen that explained the p vs np thing in a way i could understand. thanks!
@ArtOfTheProblem
3 жыл бұрын
happy you found this, stay tuned!
Best explanation of this topic I have ever come across. Brilliant!
@ArtOfTheProblem
3 жыл бұрын
glad it helped :)
This channel is very well made, keep it up!
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
3 жыл бұрын
appreciate the feedback
This is extremely well done, excellent video! Thanks for helping me finally understand this! ♥️
@ArtOfTheProblem
5 жыл бұрын
Thanks for the feedback, really proud of this video
Well done, good sir! By far the easiest to follow explanation of P and NP I have found on the web so far =)
@ArtOfTheProblem
5 жыл бұрын
Thank you, put a lot of work into this and happy it's finally helping people.
the quality of this video means you undertand well what are you talking about. I've enjoyed it, big thanks.
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
The best detailed explanation of most toughest topics like COA etc . Thankyou so much sir ❤️🙏🙏
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
3 жыл бұрын
wooo, awesome thanks for the feedback!
This is the beat N vs NP explanation I have watch. Thanks
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
5 жыл бұрын
I appreciate the kind words. I know you are being honest because before I made this video I watched everything and was disappointed
This is pure gold, by far the best explanation of P vs NP that I came across.
@ArtOfTheProblem
2 жыл бұрын
glad you found it
The best P vs NP explanation I've seen
@ArtOfTheProblem
6 жыл бұрын
thank you, I struggled with this one
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.
Very well done, not only this video but the whole channel! Keep it up 👏
@ArtOfTheProblem
5 жыл бұрын
Thanks Stefan, I'm really happy with this CS series. Currently trying to develop a similar one on AI
@StefanTheFink
5 жыл бұрын
@@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 😊
This is a really great video. Such a great explanation.
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
11 ай бұрын
awesome, glad you still found this
This is the best-explained video about polynomial time that I have ever seen! Amazing work!
@ArtOfTheProblem
3 жыл бұрын
thrilled to hear this. i worked really hard on this video and i'm glad people are still finding it
@shandou5276
3 жыл бұрын
@@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
3 жыл бұрын
@@shandou5276 wonderful :))) please do. i have more on the way
Okay, I liked this video so much I logged in on a library computer just to like and subscribe! AMAZING explanation!
@ArtOfTheProblem
5 жыл бұрын
awesome I'm thrilled this video is helping others find their way. appreciate it
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
4 жыл бұрын
SWEET! that was my goal, thrilled to hear it.
Brilliant explanation, this channel is goldmine!
@ArtOfTheProblem
3 жыл бұрын
So happy you have found this channel stay tuned for more!
Possibly the best video on the topic. Thank you!
@ArtOfTheProblem
8 ай бұрын
new vid! kzread.info/dash/bejne/gXqHm5JmdrucoMo.html
Thank you so much for the great explanation and visuals!
@ArtOfTheProblem
3 жыл бұрын
thanks for feedback
I've watched a few np vs p videos. this has been the clearest. Thanks!
@ArtOfTheProblem
3 жыл бұрын
super glad you found it
You are conveying the hard concepts amazingly well.
@ArtOfTheProblem
4 жыл бұрын
appreciate the support, please stick around!
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
4 жыл бұрын
wonderful...thank you
Chapeau. Perfect, simple explaination
@ArtOfTheProblem
4 жыл бұрын
thanks for the feedback glad it helped
It is one of the best explanation of P Vs NP. Thank you so much for explaining it in such simple way.
@ArtOfTheProblem
5 жыл бұрын
please share thank you kindly
My god, this is by far the best explanation of this topic.
Extremely well explained, wonderful video! Keep em up :)
@ArtOfTheProblem
2 жыл бұрын
thank you, glad you found it
Amazing video, helped me with understanding my course materials.
@ArtOfTheProblem
8 ай бұрын
thanks glad to hear
What a fabulous video. Thanks!
The best explanation on this topic!
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
4 жыл бұрын
so happy it's helping people
straightforward and easy to understand, and most importantly, presented in decent speed.
@ArtOfTheProblem
4 жыл бұрын
appreciate the feedback
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
6 жыл бұрын
Thanks for the feedback, I worked really hard on this one.
@kaitlyn__L
6 жыл бұрын
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
6 жыл бұрын
Thanks so much for your feedback (NP problems are EXP problems we can verify quickly). Thrilled to hear people are gradually finding this video.
Wow! What an amazing explanation he provided!
@ArtOfTheProblem
5 жыл бұрын
appreciate your feedback
Kudos , helped me finally understand P vs NP esp the non deterministic computer part
@ArtOfTheProblem
4 жыл бұрын
great to hear
Thank you!!! Like henry jacobowitz,brieske(author of world book enclopedia math stuff) & kinertia you are a master teacher!!!! 🥰🤩😁
A nice informative video. Thx
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
3 жыл бұрын
thrilled to hear it! the algorithm hates this channel I agree it sucks
Best explanation ever!!!!!!
thank you very much for your effort
Man I wish I found this video last semester
excellent as always, thanks!
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
3 жыл бұрын
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 :)
Well explained, thanks.
Welcome back!
Thank you for this video.
That was very clear! Thanks!
excellent lecture
So theoretically this will be solvable on a quantum computer in future?
@chufeng6223
5 жыл бұрын
Indeed. We just need a breaktrough in quantum physics that starts by saying "there is nothing definitite", creatint a reliable machine using non definite methodes will proove as hard as reaching sky from earth..... The problem with quantum ohysics is that its more math then physics. We have yet to be able to practicly use anything stated there so how will we make a quantum computer from it? When we "do" quantum physics we dont even have an idea what we are playing with since the things we are trying to manipulate arent waves nor particles but something else entirely that we completely destroy simply by observing it.
@MajorTom97
5 жыл бұрын
@@chufeng6223 IBM says: We do not believe that quantum computers are likely to provide any more than a quadratic speedup to NP-complete problems. This is the consensus view of the quantum information research community, and in fact the idea that quantum computers can solve NP-complete problems efficiently has been described as “the *central* crock about quantum computing”. (www.scottaaronson.com/democritus/lec10.html)
Wonderful presentation on the topic! In contrast to the usually very dry presentation in class.
@ArtOfTheProblem
11 ай бұрын
thank you, yes I know how horribly try this class can be
Great video !
Videos contain a lot of interesting and helpful information, but I must say, the music makes me feel tense.
I have found the answer. P does not equal NP and here is my proof: If we set P equal to 1 and NP equal to 0 and use the ZFC Axiom of Pairing we come up with with the set (10). Now the partition of 10, p(10) or p of ten is 42. If we refer back to Douglas Adams book "The Hitchhiker's Guide to the Galaxy" we find that the great computer "Deep Thought" found the answer to life, the universe and everything is in fact 42. And this is confirmed because Deep Thought, when pressed, exclaimed "I checked it very thoroughly and the answer is 42". However, the program ran for 7.5 million years which is quite obviously NP time. Therefore, ergo P does not equal NP ... QED ... how do I claim the Clay institute prize. Oh, I have to wait 5 years ... ?!?!!! Seriously, this is an excellent video and you have mapped out the problem the way Richard Feynman would have if he were covering this topic with his students ... Bravo! Thank you!
@ArtOfTheProblem
5 жыл бұрын
wow really appreciated the comparison obviously as he's one of my inspirations.
Best explanation on youtube
@ArtOfTheProblem
2 жыл бұрын
glad you found this
Great video, thank you
So well done
@ArtOfTheProblem
Жыл бұрын
appreciate it
Why do I even go to college bruh this is better than anything I’ve ever heard from a professor
@ArtOfTheProblem
2 жыл бұрын
Thanks Tyler, my frustration with how professors covered this lead to this channel and videos like this. down with the institutions!
Many thanks. Make my brain understand. Wow.
@ArtOfTheProblem
7 ай бұрын
thrilled to hear it
A brilliant explanation
@ArtOfTheProblem
2 жыл бұрын
glad you enjoyed
I have an algorithm where should I publish or post it?
Beautiful stuff
@ArtOfTheProblem
4 жыл бұрын
thank you luke
hope u can turn on auto-subtitle. thank you~!!
Thank you so much sir!
@ArtOfTheProblem
2 жыл бұрын
glad you found this video, i love this one
amazing
Great video! But why is the music so scary
Great video. What about NP-hard problems?