P = NP Explained Visually (Big O Notation & Complexity Theory)
Вставка
- Опубліковано 4 жов 2017
- 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
I'm still shocked at how few subscribers this channel has...truly some of the best explanations of difficult concepts I've come across.
@EZIO AUDITORE DA FIRENZE please consider supporting this program www.patreon.com/artoftheproblem
this comment just made me subscribe .. 2 years in the making
Thanks, I subscribed thanks to you
Maybe it's the irritating music.
better than some folks in computerphile
So far, this is the best video on explaining P vs NP.
glad to hear it Albert -thanks
this video is better than the p vs np video with 1.4 million views. great job!
Thank you for the feedback. UA-cam's algorithms are not biased towards this channel since I've slowed content production
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 UA-cam. Writing a comment to show my support and gratitude!!!
thank you! i know your pain and glad this finally helped
By far the best explanation of P vs. NP on UA-cam. The background on complexity theory was great to contextualise exactly what it means to define a computing problem as easy or hard. Fantastic work!
I really appreciate the feedback Siddharth, I watched every video on UA-cam and then made this one to correct the confusions. Stick around more to come
Looking forward to it. You've got yourself another subscriber.
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
I miss your videos , glad to see one today!! Very informative as usual! Thank you :)
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. 👏🙌👏👊
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!
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.
This is the best definition I have heard - until now, of this problem. Thankyou for sharing.
I have seen over a dozen P versus NP videos and this is far and away the clearest… Veritassium level clarity video.
appreciate 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.
Welcome to the party! glad you found us, i actually do have a new video comng soon
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!
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!
thank you, i made this video for this exact reason
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.
You guys are great! Well written and directed videos.
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.
This channel is very well made, keep it up!
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!
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.
wonderful to hear I appreciate the feedback, please stick around
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
appreciate the feedback
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!
excellent, that was the hope here, to address that gap which existed in my mind - I know the frustration you felt
best ever!!!
better than any university!
very creative
you have the talent of being a director, sensitive,logic, good-story teller ,knowledgeable and romantic
I have read and watched tons of material on this subject and this is hands down the simplest and clearest explanation of this problem
thrilled to hear it. I tried to read everything out there and I was striving for something much better to help people out
The best detailed explanation of most toughest topics like COA etc . Thankyou so much sir ❤️🙏🙏
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
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!!
wooo, awesome thanks for the feedback!
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.
thanks for your feedback it means a lot to me. I spent a long time trying to get this one right
@@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.
@@cubostar awesome, that's always been the goal
What an amazing video! I learned more watching this video than in my whole NP completeness class!
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
Best explanation of this topic I have ever come across. Brilliant!
glad it helped :)
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!
thank you kindly, I worked really hard on this video and I'm glad people are finding it.
@@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!
the quality of this video means you undertand well what are you talking about. I've enjoyed it, big thanks.
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!
awesome that was the idea behind this channel, following a conceptual progression through time.
This is extremely well done, excellent video! Thanks for helping me finally understand this! ♥️
Thanks for the feedback, really proud of this video
That was amazing. It was one of the best scientific explanations of a hard concept in a very clear method and easy to understand.
awesome, glad you still found this
This is such a good explanation to such a complex concept, that I'm seriously questioning whether or not I understood it.
couldn't ask for a better comment
This is a really great video. Such a great explanation.
This is the best-explained video about polynomial time that I have ever seen! Amazing work!
thrilled to hear this. i worked really hard on this video and i'm glad people are still finding it
@@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!
@@shandou5276 wonderful :))) please do. i have more on the way
This is pure gold, by far the best explanation of P vs NP that I came across.
glad you found it
This is the beat N vs NP explanation I have watch. Thanks
I think I was hypnotised by this video and it was beautifully explained. Thank you so much! Answered so many related questions I had
wonderful...thank you
You are conveying the hard concepts amazingly well.
appreciate the support, please stick around!
Thank you so much for the great explanation and visuals!
thanks for feedback
Very well done, not only this video but the whole channel! Keep it up 👏
Thanks Stefan, I'm really happy with this CS series. Currently trying to develop a similar one on AI
@@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 😊
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!
fantastic glad to hear it. That was the goal of this video as I never found the existing ones satisfying
@@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?
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.
Well done, good sir! By far the easiest to follow explanation of P and NP I have found on the web so far =)
Thank you, put a lot of work into this and happy it's finally helping people.
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 !!
I appreciate the kind words. I know you are being honest because before I made this video I watched everything and was disappointed
Brilliant explanation, this channel is goldmine!
So happy you have found this channel stay tuned for more!
first video ive seen that explained the p vs np thing in a way i could understand. thanks!
happy you found this, stay tuned!
It is one of the best explanation of P Vs NP. Thank you so much for explaining it in such simple way.
please share thank you kindly
Possibly the best video on the topic. Thank you!
new vid! ua-cam.com/video/OFS90-FX6pg/v-deo.html
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 :(
Thanks for the feedback, I worked really hard on this one.
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!
Thanks so much for your feedback (NP problems are EXP problems we can verify quickly). Thrilled to hear people are gradually finding this video.
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 🧠✨
so happy it's helping people
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!!!
SWEET! that was my goal, thrilled to hear it.
My god, this is by far the best explanation of this topic.
Okay, I liked this video so much I logged in on a library computer just to like and subscribe! AMAZING explanation!
awesome I'm thrilled this video is helping others find their way. appreciate it
straightforward and easy to understand, and most importantly, presented in decent speed.
appreciate the feedback
Amazing video, helped me with understanding my course materials.
thanks glad to hear
The best P vs NP explanation I've seen
thank you, I struggled with this one
The best explanation on this topic!
I've watched a few np vs p videos. this has been the clearest. Thanks!
super glad you found it
Extremely well explained, wonderful video! Keep em up :)
thank you, glad you found it
Kudos , helped me finally understand P vs NP esp the non deterministic computer part
great to hear
Wonderful presentation on the topic! In contrast to the usually very dry presentation in class.
thank you, yes I know how horribly try this class can be
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.
awesome glad this helped
Wow! What an amazing explanation he provided!
appreciate your feedback
What a fabulous video. 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! 👍👍👍😁😁
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 :)
Oh, damn. I didn't realize that Nash (as in Russell Crowe in _A Beautiful Mind_) also contributed commentary on this subject, but it makes sense given his strong relation with cryptography.
yes I was surprised to see this too
thank you very much for your effort
Videos contain a lot of interesting and helpful information, but I must say, the music makes me feel tense.
Welcome back!
Well explained, thanks.
hope u can turn on auto-subtitle. thank you~!!
Hi! can you make another video about NP Hard? your video made me understand this concept more than any other material
A nice informative video. Thx
excellent as always, thanks!
excellently explained, thanks so much. please turn the background music down though - i found it really distracting.
Fascinating Theory! I am a CS student and I am still struggling to comprehend these big ideas.
Excellent I made this video for students like you
Chapeau. Perfect, simple explaination
thanks for the feedback glad it helped
Great video !
That was very clear! Thanks!
Thank you for this video.
Best explanation ever!!!!!!
Thank you!!! Like henry jacobowitz,brieske(author of world book enclopedia math stuff) & kinertia you are a master teacher!!!! 🥰🤩😁
7:18 I don't think that's what "reduction" is. Reduction doesn't mean reducing a problem in the sense of making a problem 'easier'. Reductions are basically conversions. We reduce a problem A to problem B knowing that B is at least as hard as A, i.e., A is at most as hard as B. If B is P, A is P. If B is NP, A is at most NP (A could be P in truth but since P is a subset of NP, it still holds).
Great video, thank you
A brilliant explanation
glad you enjoyed
Could you make a video about e being more important than pi.
The reason is that pie is just about circles. But e is about the growth of nature … everything … it governs the shape and scale of macro reality itself.
it's true...thanks for the note. in terms of next i'm finishing ai, and then i'm thinking either economics or physics...both involve e...
Great video. What about NP-hard problems?
loved the video a lot ❤❤❤❤❤
stay tuned
I use so many loops whenever making in game in my programming … when I starting programming I didn't understand all that performance so I kept adding more loops to make life better but my game use to run super slow in realtime cause of the loops I used…. I also figured if I put a loop which has a condition that is always true.. so the loop will infinitely run every frame, game crashes immediately.
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!
wow really appreciated the comparison obviously as he's one of my inspirations.
Thank you sir ❤
thank you, loved making this one
excellent lecture
Man I wish I found this video last semester
Thank you so much sir!
glad you found this video, i love this one
So well done
appreciate it
Best explanation on youtube
glad you found this