P = NP Explained Visually (Big O Notation & Complexity Theory)
HTML-код
- Опубликовано: 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
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. RUclips'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 RUclips. Writing a comment to show my support and gratitude!!!
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.
appreciate it
By far the best explanation of P vs. NP on RUclips. 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 RUclips and then made this one to correct the confusions. Stick around more to come
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!
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, hands down, the most beautiful and clear video on this topic I've watched.
wonderful to hear I appreciate the feedback, please stick around
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'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. 👏🙌👏👊
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!
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
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
I miss your videos , glad to see one today!! Very informative as usual! Thank you :)
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
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 pure gold, by far the best explanation of P vs NP that I came across.
glad you found it
This is the best definition I have heard - until now, of this problem. Thankyou for sharing.
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
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
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!
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
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.
couldn't ask for a better comment
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.
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.
Best explanation of this topic I have ever come across. Brilliant!
glad it helped :)
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
Also the best P vs NP explanation I've ever seen. Your channel will explode in popularity, just give it time.
first video ive seen that explained the p vs np thing in a way i could understand. thanks!
happy you found this, stay tuned!
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!
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
This channel is very well made, keep it up!
This is extremely well done, excellent video! Thanks for helping me finally understand this! ♥️
Thanks for the feedback, really proud of this video
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
The best detailed explanation of most toughest topics like COA etc . Thankyou so much sir ❤️🙏🙏
the quality of this video means you undertand well what are you talking about. I've enjoyed it, big thanks.
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 😊
Brilliant explanation, this channel is goldmine!
So happy you have found this channel stay tuned for more!
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 a really great video. Such a great explanation.
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 the beat N vs NP explanation I have watch. Thanks
The best P vs NP explanation I've seen
thank you, I struggled with this one
You are conveying the hard concepts amazingly well.
appreciate the support, please stick around!
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.
Possibly the best video on the topic. Thank you!
new vid! ruclips.net/video/OFS90-FX6pg/видео.html
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
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
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.
Thank you so much for the great explanation and visuals!
thanks for feedback
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
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
Extremely well explained, wonderful video! Keep em up :)
thank you, glad you found it
Man I wish I found this video last semester
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.
Amazing video, helped me with understanding my course materials.
thanks glad to hear
I've watched a few np vs p videos. this has been the clearest. Thanks!
super glad you found it
The best explanation on this topic!
Chapeau. Perfect, simple explaination
thanks for the feedback glad it helped
What a fabulous video. Thanks!
My god, this is by far the best explanation of this topic.
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.
Videos contain a lot of interesting and helpful information, but I must say, the music makes me feel tense.
A nice informative video. Thx
Wow! What an amazing explanation he provided!
appreciate your feedback
Best explanation ever!!!!!!
Well explained, thanks.
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
Kudos , helped me finally understand P vs NP esp the non deterministic computer part
great to hear
thank you very much for your effort
excellent lecture
excellent as always, thanks!
That was very clear! 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
Thank you for this video.
Thank you!!! Like henry jacobowitz,brieske(author of world book enclopedia math stuff) & kinertia you are a master teacher!!!! 🥰🤩😁
Welcome back!
Best explanation on youtube
glad you found this
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
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 !
Great video, thank you
Many thanks. Make my brain understand. Wow.
thrilled to hear it
A brilliant explanation
glad you enjoyed
thanks very great amazing story thanks!!
Thank you so much sir!
glad you found this video, i love this one
Thank you sir ❤
thank you, loved making this one
So well done
appreciate it
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!
Great video! But why is the music so scary
loved the video a lot ❤❤❤❤❤
stay tuned
hope u can turn on auto-subtitle. thank you~!!
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
Best ever!
So theoretically this will be solvable on a quantum computer in future?
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.
@@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)
Beautiful stuff
thank you luke