P = NP Explained Visually (Big O Notation & Complexity Theory)
Vložit
- čas přidán 4. 10. 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
So far, this is the best video on explaining P vs NP.
glad to hear it Albert -thanks
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
this video is better than the p vs np video with 1.4 million views. great job!
Thank you for the feedback. CZcams's algorithms are not biased towards this channel since I've slowed content production
I have seen over a dozen P versus NP videos and this is far and away the clearest… Veritassium level clarity video.
appreciate it
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 CZcams. 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 CZcams. 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 CZcams 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 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
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. 👏🙌👏👊
This is the best definition I have heard - until now, of this problem. Thankyou for sharing.
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.
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
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'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 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
You guys are great! Well written and directed videos.
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'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.
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
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
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.
Also the best P vs NP explanation I've ever seen. Your channel will explode in popularity, just give it time.
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
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!
This channel is very well made, keep it up!
The best detailed explanation of most toughest topics like COA etc . Thankyou so much sir ❤️🙏🙏
Best explanation of this topic I have ever come across. Brilliant!
glad it helped :)
the quality of this video means you undertand well what are you talking about. I've enjoyed it, big thanks.
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
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 is extremely well done, excellent video! Thanks for helping me finally understand this! ♥️
Thanks for the feedback, really proud of this video
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 is the beat N vs NP explanation I have watch. Thanks
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.
This is a really great video. Such a great explanation.
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 😊
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
This is pure gold, by far the best explanation of P vs NP that I came across.
glad you found it
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 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!
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
Possibly the best video on the topic. Thank you!
new vid! czcams.com/video/OFS90-FX6pg/video.html
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
Thank you so much for the great explanation and visuals!
thanks for feedback
I've watched a few np vs p videos. this has been the clearest. Thanks!
super glad you found it
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
first video ive seen that explained the p vs np thing in a way i could understand. thanks!
happy you found this, stay tuned!
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
Brilliant explanation, this channel is goldmine!
So happy you have found this channel stay tuned for more!
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.
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
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
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
The best explanation on this topic!
Amazing video, helped me with understanding my course materials.
thanks glad to hear
What a fabulous video. Thanks!
My god, this is by far the best explanation of 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 🧠✨
so happy it's helping people
Chapeau. Perfect, simple explaination
thanks for the feedback glad it helped
Extremely well explained, wonderful video! Keep em up :)
thank you, glad you found it
Wow! What an amazing explanation he provided!
appreciate your feedback
straightforward and easy to understand, and most importantly, presented in decent speed.
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 :(
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.
The best P vs NP explanation I've seen
thank you, I struggled with this one
Best explanation ever!!!!!!
thank you very much for your effort
excellent as always, thanks!
That was very clear! Thanks!
Kudos , helped me finally understand P vs NP esp the non deterministic computer part
great to hear
Welcome back!
Well explained, thanks.
Great video !
A nice informative video. Thx
Thank you for this video.
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 :)
Great video, thank you
Man I wish I found this video last semester
Many thanks. Make my brain understand. Wow.
thrilled to hear it
So well done
appreciate it
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
Best explanation on youtube
glad you found this
Thank you!!! Like henry jacobowitz,brieske(author of world book enclopedia math stuff) & kinertia you are a master teacher!!!! 🥰🤩😁
A brilliant explanation
glad you enjoyed
Amazing video, thank you!
appreciate the feedback!
@@ArtOfTheProblem I was struggling with this concept for quite some time, but this was a great explanation. Keep up the good work!
Thank you sir ❤
thank you, loved making this one
excellent lecture
loved the video a lot ❤❤❤❤❤
stay tuned
Thank you so much sir!
glad you found this video, i love this one
Videos contain a lot of interesting and helpful information, but I must say, the music makes me feel tense.
Really great !
glad you found this
Beautiful stuff
thank you luke
thanks very great amazing story thanks!!
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!
thrilled to hear it! the algorithm hates this channel I agree it sucks
Best ever!
Hi! can you make another video about NP Hard? your video made me understand this concept more than any other material
this is amazing!
awesome glad you found it
You helped me a lot! Thank you so much!
Excellent.