P vs. NP and the Computational Complexity Zoo
Vložit
- čas přidán 25. 08. 2014
- Hackerdashery #2
Inspired by the Complexity Zoo wiki: complexityzoo.uwaterloo.ca/Co...
For more advanced reading, I highly recommend Scott Aaronson's blog, Shtetl-Optimized: www.scottaaronson.com/blog/
-----
Retro-fabulous, cabinet-sized computers:
System/360: en.wikipedia.org/wiki/IBM_Syst...
photo: "360-91-panel". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/Fil...
PDP-8: en.wikipedia.org/wiki/PDP-8
photo: "PDP-8". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/Fil...
-----
Protein folding illustration: "Protein folding schematic" by Tomixdf (talk) - Own work (Original text: “self-made”). Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/Fil...
P vs. NP opinion poll: www.cs.umd.edu/~gasarch/papers...
programming interviews: If you'll prove that P = NP then we'll hire you as an intern
Let's say a specific problem expected to be NP turns out to be P, but with a ridulously high power, say N^100. How does that help? It still requires approximation methods that find local optimums, like genetic programming.
@@TheGandorX Well none of the np complete problems have ever been found to =p. Thats the problem, but its has yet to be proven that they cant = p either.
True af
Only Indians were interviewed
@PotatoTornado You cant turn a P problem into a np complete problem.
Your quotes at the end of the video made me think of this one: "I didn’t have time to write a short letter, so I wrote a long one instead." - Mark Twain
I prefer "If I had more time, I would've written a shorter letter."
;)
Behind simplesty there is a long story
Mark Twain is possibly my favorite writer. Very intelligent and wise.
@@nathan3721 Indeed!!!
The fact that coming up with a really fast method of solving sudoku could basically fast track *curing cancer* is mindblowing
True, thing is most of us agree that P is most likely not equal to NP
Still, non deterministic polynomial algorithms for such problems can still be faster or slower compared to each other and there's a lot of work that goes into making them as fast as possible, usually in the form of SAT-solvers (a nice keyword for you to google more detail there)
Curing cancer is almost an impossibility but averting cancer through a healthy diet is possible. You people constantly blow my mind. I would like to ask you people one question. Why are you people not vegan? That is how to almost eradicate cancer. That is how to end the worldwide obese epidemic. That is how to stop our species degenerating. That is how to save the planet and all the species on the planet. That is how we will evolve. I do not understand the complexities of mathematics. That is what you people excel at but could you people please go vegan and then direct your brilliant minds to building a vegan world. Time is running out for planet earth and all the species that live on it. Thank you.🌱
Math is wild
This is just an amazing video
- dynamic
- pauses between sentences are short
- music keeps you focused
- the story is made of only simple words used to explain complex concepts followed by very simple visual examples from real world
- the pace is so right
Ivan R yea man I enjoyed it
@LeDjipy Just watch it with subtitles and slower speed, figure out with vocabulary first and pronunciation. There is a settings -> playback speed.
I didn't get most of it
Music only distracts. Your brain has to process one extra task - the music. So no, music is not what makes you focused. Your attention is.
No it's not! it is bewildering.
understanding why someone would dislike this video is an NP problem
edit: since my comment got so many likes and it might be seen by the authors of the video, i'd like to ask them, on behalf of the 56k people who liked this video, for more. this is one of my favorite videos on youtube.
no this is halting problem
ITTM-undecideable
They voted Brexit/ Trump
The reason why someone may dislike this video is because this video doesn’t inspire. And no, it’s not simple. The video is lots of art, sure. But no viewer with coding experience will think, “ok, here is the goal, let’s take it step-by-step” because a model was not first developed.
@@danielmontaigne1219 There are no smart Brexit/Trump supporters. People who think different than me are dumb and I'm better than them because I liked this video.
Quite a way to think, eh?
Welp, time to look up those six other problems. There goes my night.
Six Millions waiting there :)
Wish he could have cited the fundamental papers for each set then provided he own sources via link to wikis or books.
If you solve P=NP, the others are easy
Luiz Felipe Except if you solve it by proving P≠NP
Someone truly understood the video
I'm a computer scientist with a PhD in combinatorics and this is easily the best explanation of the P = NP problem I have ever seen, and I've seen it and had to try to explain it many times. Awesome video.
having a phd doesn't mean you're smart or bright or creative
@@mojo5093Thank you for your enlightening contribution! Oh wait...
@@celkat He's not wrong
@@mojo5093 Your comment has no relevance to what I said. I mentioned the PhD to imply that I have been introduced to / introduced the P = NP problem dozens and dozens of times and much more often than most people,, and this is the best presentation I've seen of it. I was congratulating the video producer on a job well done.
Then you come onto a conversation, misunderstanding why something has been stated, and leave a snarky "rebuttal" to a claim I never made?
That's a pretty strong indication that you're not particularly smart, bright (synonyms), or creative. Do you feel better about yourself now?
Your comment supports that there is a growing general disdain against education. If this was a conversation about a football topic and had I come in here and said I was on the college football team as QB and this was one of the best explanations I'd heard of that topic, Im willing to bet that you wouldn't have opened your mouth to make a comment about my mention of being QB; however, since my claim is academic instead of physical, you feel some strange need to come in here and be snarky.
@@rope435 HIs comment has nothing to do with the conversation. I mentioned that I have a PhD in combinatorics not to give myself authoritative validity or imply that I'm smart or bright or creative, but to say that I've seen and studied the P=NP problem more often than most people since it's in my field of study and I use it at work. Then I used that to give a much deserved thumbs up to the author for giving the clearest, concise, easy-to-understand description of the P = NP problem, at which point, MO JO lasered in to my mention of my PhD, inferred that I was implying a whole bunch of things that I was not, and contributed nothing of value or even on topic to the conversation.
See my reply to him on this thread. I don't know if you have a disdain for education, but there is certainly a growing one. My personal hypothesis is that it's pure Dunning-Kruger.
I’m a simple man. I see something I don’t understand, I click
If you keep doing this you won't be a simple man for too long
Me too 😂😂😂😂
curiosity
Run out of clicks pretty soon.
You are simple, you can’t even come up with an original joke
"If P=NP everyone who could appreciate a symphony would be Mozart"... what an amazing way to resume/explain the implications of P=NP
I would say "could be Mozart" would be less biased, because P=NP only implies that for every problem whose solution can be easily checked (NP), there is a method that can systematically resolve it (within only a polynomial number of step). But not that being able to check a solution would automatically imply discovering that method.
@@youri76000 Exactly
@@youri76000 Yes, this is slippery. There is the intermediate case you allude to.
@@worldnotworld which one?
@@youri76000 It is a little bit biased. But it is reasonable for deterministic problems, because you can always (1) randomly generate some answer by RNGs and (2) check if it's correct, both in polynomial time, all intention to "discover a method to systematically solve a problem efficiently" would end up to be just as good as "guessing the answers".
I am a senior in software engineering at the University of Nevada, Las Vegas and I found this video to be one of the best videos out there on CZcams. Not only it inspires us scientists to continue trying to solve P vs NP, but it also shows the world the importance of time complexity and how it affects our lives.
You also as a programmer, have to give some thought as to how long an operation might take to be performed. If it often takes too long, then the user needs a progress thermometer, so that it does not appear that their computer software has just frozen or crashed for no apparent reason, then they start doing drastic things that could cause problems, such as force-quitting. Also, any data file updates should be done in such a way, that if the program becomes interrupted, the data is quite unlikely to become corrupted. Thus, perhaps the old state of the files is maintained as the current version, completely until all updates have been completed. Thus, the worst-case scenarios is simply starting the process over again, and not catastrophic data loss.
BTW, I notice that some progress thermometers, initially have no idea how long the process will take. Rather, they self-calibrate and will estimate how long, based upon the rate that it is progressing so far after a short wait going into doing the process.
@@yosefmacgruber1920This is what RAID controllers are for.
Also the reason progress bars start out without an accurate estimate is because that calculation itself is quite complex. So you need a download bar for the download bar...
@@deoxal7947
The calculation is quite complex, due to factors beyond the computer's control. For example, the hard drive or even USB flash drive has its own computer controlling it. You can't tell it to hurry, it takes as long as it takes. The computer doesn't even know how long it takes, unless it can find that data in the device driver or in some database, other than by testing or bench-marking it. Some devices are faster, some are slower. Or if downloading, the speed of the internet and wifi links, affects it, and maybe the server is running slow today.
When progress bars start without an estimate and take several seconds or more to estimate, that is because the computer is trying to get a small test percentage done, and it times the progress against its own internal clock, and then extrapolates "At the current data flow rate, 2 minutes are remaining." If then it becomes 3 minutes and 5 minutes, it is because some weak link in the data flow, is slowing things down.
There are a few self-explanatory progress bars for progress bars. The empty bar appearing, and meaningless movement or gradients flowing in it, before it starts properly advancing. Some progress bars never properly advance, because for some reason, it doesn't even seem to know how big the file is, and so it just shows progress, but not the percentage of completion. It could be because of a gap in the programming, that it is not fully compatible, so some of the progress calculation data is missing. Sometimes, well especially in a free or beta version, it is more important that it works, than just how great its performance level is. The circle going around, that often means, hold on for a moment, I actually am doing something. And to have better self-explaining error messages would be helpful. "Internet connection is not responding, attempted to reset the connection." "Re-requesting the file, due to request time-out." I get so tired of crappy software, in which the circle or beachball goes round and round, and you walk away for a minute and come back, and still nothing has happened. Surely a computer can diagnose when no progress is occurring or when the data link has gone down and do something appropriate about it. Not just tease the user and pretend to be working on it.
When I was in college long ago, and the Macintosh lab was jam-packed with users, I tried a curious experiment. I needed to make a copy of an 800K Mac-formatted 3.5" disk. Problem was, I had no Mac. I had an Apple //e computer with a mail-order 800K disk drive. Hmm. Both computers made by Apple. Both 800K, both using the same type of disks. Hmm. I suspected they could be undocumentedly compatible, even though supposedly they were not. I ran a disk copy. The copy disk verified noticeably faster than the Mac original. Wow. Really? An improvement? Not so much. I knew enough about how they work, to know what had happened. My Apple //e used the wrong sector interlace ratio. It used 4 to 1, and it was supposed to use 2 to 1 for Macintosh. 4 to 1 only optimized it for use on my //e and not on the Mac. That incorrect ratio Mac disk would run slower on a Mac. 4 disk spins would be required to load the entire track, where otherwise it would only need 2. That was back in the days, when most all the work was dumped onto the CPU. The //e was so slow, that it needed a 4 to 1 ratio, to have enough time to process the disk data before it could be ready to read the next sector. The Mac 2 to 1 ratio was causing it to miss the next consecutive sector, and so it had to wait for an entire turn of the disk to read the next sector. My copy disk worked just fine on a Macintosh. That told me in theory at least, that an Apple //e computer could technically be programmed to see, load, copy Mac files, as it was actually capable of reading and writing the data. (My interest was in writing my own OS, and also in being able to use Mac fonts on my //e.) The compatibility problem was not critical, as it did not keep it from working, only messed up the optimization. Better software could have chosen the correct ratio for Macintosh. But I guess cross-platform programming wasn't quite as big a thing as it is now?
Another interesting experiment, slightly related. I liked the music on a PS1 pinball game CD. Since the PS1 often used actual CD tracks for game music, I once put the CD into my car CD player. It didn't play at first, but I pushed the next track button, and it easily played the game music. Apparently it was some sort of hybrid disk, with a game data track, and standard CD audio tracks. I doubt that that would work on later video game console disks, because I think their music tended to be some sort of compression. And earlier CD-ROM drives were actually CD players as well, meaning that they have actual audio outputs that were connected to the motherboard. I suppose if the computer crashed and froze up, the music would keep on playing? I think they may have moved away from that now, as computers became faster, perhaps the computer actually does the work of playing the CD/DVD, streaming the data, and doing all that drawing of the movie image to the computer graphics memory. And where is that "audio connection" when your optical drive now has no connection at all to the computer other than a USB cable? Surely is it 100% computer data now?
Normally, I am not much bothered by a progress thermometer. They usually fill up fast enough. I just want to see that it is progressing and that the computer hasn't crashed or froze up. I had an experimental program that I wrote on my graphing calculator, that had to momentarily display a graphic image on the screen, so that it could use it as efficient storage to load all of its graphic icon variables. My little progress thermometer filled in just a second or two. Just drawing/updating the progress thermometer, probably slowed down the load by 30%?
Very interesting read, I didn't expect such a long post. I heard about playing audio from CDs with other content on them from this video about malware. czcams.com/video/4eM4wjgXsJI/video.html
Also I found this xkcd about progress bars. www.xkcd.com/612
I forgot to ask, what was the program you made for the calculator? Do you still have it? I'd like to see it if possible.
I first saw this view in 2016 while in high school and falling in love with math. I no longer love math the way I once did, but I still return to this video at least once a year. There's something so profound in it that never ceases to blow me away.
Still sad this channel stopped at this video
Umm...you need to make more videos
ikr
+behnamasid2 yah. did he, like, die?
For Real.
I will pay money to watch more videos!
Welch Labs you also great explianer.
I love when someone can make a 10 min video that conceptually explains a CS topic better than my grossly overpaid professor that can't take the time to make decent slides. Great video!
Your prof is there to further their research, teaching you is just sidework. The maker of this video is highly incentivised to communicate the concept clearly and in an engaging way. Yet only one is considered to be a valid form of "education." The world's a funny place
DeanoTXR53 I would like to think that a professors first priority is to further a students education and passion. I would like to think they are “highly incentivized” to create meaningful and easy to understand lectures since they’re getting paid 6+ figure salary.
@@scotthofbauer5448 I would "like" to think that too... But sadly that's not the reality of why they are actually being paid that 6 figure salary. They are actually being paid for the non-classroom work/value they bring the university
@@DeanoTXR53 Not always true. There are plenty of professors who don't do much research. This is especially true at smaller, libear arts schools
@@blownspeakersss We are both correct. The ones you're talking about aren't grossly overpaid. The ones who publish research and books usually are because they offer more reputational value to the institution. Not saying it should be this way. But sad facts are sad facts
God, everytime I feel down and depressed, I visit this video and it breaks my heart because it is such an achingly BEAUTIFUL video ... Thank you Mister Hackerdashery ... 😥
As a CS student who is currently lost in my Algorithms class, I want to express my sincere thanks for making a video that explained P=NP in such a simple, easy-to-understand way. Thank you so much!
How is this in your Algorithms class? dont you have a couple Computational Theory classes?
I wouldn't have thought a video on mathematics could make me this emotional... Thank you.
because it came from the warm, loving, heart of Computer Science, not the cold, emotionless, beast known as mathematics
Glad I'm not the only one; I finished watching it and had a profound urge to cry.
@@TheAlmightyCon this is a math subject, computer science is about wrestling with dumb syntax that makes no sense
Some guy accidently linked this video on a discord server, now the whole server is watching a playlist of computer complexity.
Yooooo send it to me lol
I had a frustrating start in my day reading the unreadable script from my university about P/NP. And then I found this video which made the explanation really fun to watch! You saved my day!
Every once in a while, I come back to this video and am blown away by the amazing explanation every single time.
*_“One day I will find the right words, and they will be simple.”_*
I can't explain why but this quote moved me.
who said this
@@wongpentelglobal Jack Kerouac
"Simple." - Jack Kerouac
@@wongpentelglobal watch the video from beginning to end 👿
P Vs NP!
Who's won? Who's next? You decide!
Adam Katav good one 😀
I think this rap battle would have ended with P and NP having an existential crisis, not being sure whether they are one.
"Am I you, are you me?"
🤣🤣🤣
Epiccc rap battle of historrrrrrryyyyyy
Wow, this video was a work of art, simple yet profound, loved the music choice too absolutely perfect!
This 10-minute video could take dozens of hours to make, but it pays off awesomely in that it can be the best explanation of P and NP, ever. What an awesome video
Wow.
It's ironic how simply you explain computational complexity itself.
The pacing, visuals, examples and choice/order of subjects were all excellent.
Thank you sir
Anwser is3584
@@foobarmaximus3506 not true, E=mc^2, or more generally, E^2=p^2c^4
2+m^2c^4, is used all the time. The energy and mass in it are both well defined, and can be thought of as emerging from lagrange mechanics due to symmetries (noethers theorem).
"Everyone who could appreciate a symphony would be Mozart, everyone who could follow a step-by-step argument would be Gauss."
Nope, I'm not crying. Just got a traveling salesman caught in my eye.
lol XD!!!
hahahahhahahah damn underrated comment!
Many years ago (like 1985) I took my favorite class in computer science where we spent an entire semester basically working up to understanding the "Does P = NP?" problem. I even had a well-selling t-shirt made up with that question on it. This video does an excellent job getting the basic idea across in ten minutes.
I never comment on a video. But the sheer depth and amazing complexity explained in such a simple way was something I never expected to see in a video. Thank you very much!
I solved this in middle school. If N is an integer where N equals 1, then P = NP. Checkmate, computer science nerds.
+hameed lol
+hameed Someone get this man a dunce cap
+hameed What are you going to buy first with $1,000,000?
lol that is not one it means
+Noah Reichert prove it.
0:45 The Clay institute never actually awarded this prize, because the mathematician who solved the Poncaré conjecture refused it.
he didn't accept both the 1M $ and Fields Medal
Tony Raubenheimer i respect that guy alot
Refusing a prize doesn't mean it hasn't been awarded.
grigori perelman
@@Theo_Caro if I try to award you a prize for being a dbag and you refuse it would you go around saying the prize was awarded?
Almost 6 years later, this video is still (one of ) the best videos on this topic! Nice work!
This is just such a great video! I seem to watch it again every couple of years.
Only one way to settle this...
P VS. NP
ROUND 1!
FIGHT!!!
Jon I think we are on round O(n!). But I can't tell when P vs NP is supposed to halt.
FrankenPC Also, this round is EXP.
@@metachirality: That's one of the best comments I've seen in a long time right there
oh my god a buttload of work went into this video
QAQ your chalk numbers are so nice
Yours is one of the best videos I've watched on CZcams. I love the philosophical side of the video, thank you!
One of the most inspiring and delightful videos I've ever seen on CZcams in a long time. Thank you!
Wow. This is by far the most polished and clear explanation of the P vs NP problem and its implications, that I've seen. Props to you on your quality work and attention to detail. *Subscribed*
Fascinating subject presented in a great way. Awesome work. Please consider making more videos.
When you could cure cancers by solving sudoku
He said the nature of the problem is same, the computational complexity of solving sudoku and curing cancer through solving protein folding problem is same, a computer that can solve one such problem can also solve the other.
This is one of the best videos I've ever seen on this platform. Great job!
Speaking as a complexity theorist myself, this is a really, really great explanation -possibly the best I've ever heard. Great work! You're gifted at this, so please make more videos!
I cried watching this... please make more videos.
Gosh. I hope the uploader would continue with these amazing, beautiful, masterpiece of videos. All the best to you, sir.
It is an eye opening video for me. Will watch it multiple times with full concentration to absorb all the stuff again. Adding it to my favorites. Thanks for creating such stuff and making it accessible to all of us for free. It is inspiring stuff !
We talked about this in my artificial intelligence class, but it was completely disconnected from the other topics we were discussing and not explained very well. Noone understood why we were discussing it and we found it very mundane. Now I just stumbled across this video and *holy sh*t* you have awoken my interest in this topic! Great job and excellent video!
Awesome video! This is by far the best simple explanation of P vs. NP that I have come across in my 15+ years in CS.
This video is so good that I come back and watch it every now and then. Please make more videos!
Amazing Video. Seriously, the best one i found to be able to understand the P vs NP problem.
Thank you.
This video along with the problem is so amazing that I feel like viewing it multiple times. Love it
Excellent! I haven't heard anyone describe P and NP this well since my Computability Theory and Formal Languages class in college. P = NP captivated my mind for a while... it's great to see an awesome video about it. Well done!
This remains a phenomenal video. Given the time that's passed, it seems unlikely that we'll see more, but I wish we could. I've been subscribed for years, just waiting!
What happened?
why aren't there any more videos from this channel? Educational channel such as these shouldn't stop existing. We need them.
Absolutely amazing. I was studying for a test when I came across this video, forgot about the test itself because I was so interested in the video.. You made it much more interesting than my textbook!
Please please please make more videos! This was awesome!!
I've done three university classes where an attempt was made to explain P vs NP, and all three times i struggled to fully understand it. i wish i had come across this video sooner! the exposition and examples helped me a lot, not only to understand the topic but also what makes it interesting and worth learning about to begin with. thank you so much.
I think you are the best content creator who talks about problem solving and categorising! Nice, imaginative, and tidy drawings, cool!
What a brilliant presentation! There are so smart people around the world who invests great time and great efforts to move forward knowledge! Thank you for this entertaining presentation! Thank you so much!
One of the best videos I ever watched on computer science! Very well presented!!
One of the best profound videos found in P and NP space. Kudos !!!
I was trying to understand from videos in my mother tongue. However, the confidence, clarity and exuberance which pervades from the speaker's voice reaches straight inside with clarity. Kudos and thanks!
Literally THE BEST VIDEO on youtube I've ever seen. I can't thank you enough for this. Gave me chills.
How do you only have two videos? the other is from 3 years ago claiming you want to make more, why did you wait so long man. This was so easy to understand even for some one who's never taken computer science before. Thank you. I subbed.
One of the best explanation I have ever seen on those concepts. Thank you!
Out of all the categories of the videos that I have seen to date on CZcams, this is one of the top best video.
wow, best video on p vs np. Please do more videos about science
Why did this channel start so amazing and stopped after 2 videos ? =(((
Life got busy! I've been working on writing a new one recently.
Hey, I don't usually comment on videos much but I have to say that this video is one of my favorites, as a recent Computer Science graduate and Software Engineer. Glad to hear you're making another! :)
Please do, take your time, not polynomial time please ;)
There is some other topics em computer science closer to the subject that if explained using this form of explaining, visual, entertaining and simple can be really helpful and even fun to watch.
Hey, that's awesome to hear! Thanks for all the time you put into these.
Can't wait
I was brought here by my algorithm class. My jaw dropped when I finished watching. It's like a piece of art, amazing.
The best ever video I have seen over this topic. Great content, Great effort mate! Your videos are excellent and you should start making more such. All the very best for you. Cheers.
"I'm gonna start an educational CZcams channel... Nope. Changed my mind."
Exact my thoughts. It could have been one of the greatest CZcams educational channels ever. What a loss.
Maybe the next video is a follow-up, with a proof for P Vs NP
Maybe finding a good idea for their next video turned out to be an NP problem...
The creator of this channel is Steven Hazel of Sauce Labs. Happy to see he's doing well for himself
hey bro i can't find him😣
This is my most favourite CZcams video. I watch this at least once every month.
One of the most beautiful videos I have ever seen in my life. Uplifting experience.
Thank you for this great video. To make it even perfect, you could fix a small linguistic mistake at around 5' 30": poly-nomial comes from ancient greek poly = many and ancient greek nomos=law. If the second part would come from latin nomen=name, it would be polynominal.
You could correct this by putting in a subtitle with this info at the appropriate place.
Anyway, excellent work. I subscribed. Looking forward to your next productions.
***** Thanks for the correction! I researched this somewhat casually, and looking deeper it seems my sources were incorrect.
+B. Michael Zimmermann Irrefutable proof that one cannot flim flam the zim zam.
Additionally,
I, too, subbed.
+hackerdashery
I am greek and i dont agree with B. Michael Zimmermann's correction.
polynomial in greek does not include the word "nomos", since the word in greek is "polyonimo" ("nomos" cant be changed into "οnimo").
By googling it in greek sources, it turns out to be a half greek half latin word from greek poly=many and latin binomium = binomial (which makes perfect sense) and comes from F. Vieta.
+stkyriakoulisdr I also think Michael is wrong. All the sources I find say that polynomial was formed by analogy from binomial. And binomial was derived from Latin nomen = name. To add one more clarification: the Latin word was binomius, which became binomial in English (the -al ending is for making nouns in English).
+B. Michael Zimmermann
'polynomial' was modeled after 'binomial', coming from Latin 'binomius', or "two-named".
source: polynomial and binomial on etymonline.com
This is an amazing channel you've got going here! Please don't stop :)
Helder Ribeiro Thanks! I've got another one coming for sure.
@@hackerdashery Still Waiting...
@@SK-yo5nl Still waiting! What ever happpened to this guy? Two great videos, then nothing more...
this is an amazing video. so well put together, love the chalkboard style, clearly presented. good good job
A truly marvellous explanation in a very nice format. Well done!
🎯 Key Takeaways for quick navigation:
00:31 🧩 The P vs. NP problem is a fundamental question in computer science that asks whether problems with quick verification (NP) also have quick solutions (P), and solving it has profound implications for various fields.
04:12 📈 The difficulty of the P vs. NP problem lies in how the difficulty scales up as problem size increases, which impacts the efficiency of computer solutions.
05:38 🔢 P represents problems solvable in polynomial time, while NP involves problems where a correct solution can be checked in polynomial time. NP-complete problems are the most challenging in NP.
07:30 🎮 NP-complete problems, like Sudoku and protein folding, share a common underlying complexity, suggesting that fast solutions may not exist.
09:50 🌐 The P vs. NP question has far-reaching implications, potentially reshaping our understanding of creativity, art, and the fundamental nature of computation in fields like physics and biology.
Obligatory "Y U NO MAKE MORE VIDS" comment.
Seriously man, you could really have something here.
@@foobarmaximus3506 NP problem bud
This is the best thing I've ever seen in my entire life. It is better than any movie ever made. Better than any TV show you watched. Better than any lecture you attended. This is peak lecturing and peak entertainment.
Wow great video!!! So clear, so focused...so powerful in informing. Thank you!
I have studied computer science and I really really have to commend your video.
It is one of the best informational I have ever seen, it ramps up from ELI5 to stuff I hadnt even head at all,
while keeping a great presentation and ending on a touching note.
Anyone can appreciate the video and quit when the video surpasses their expertise or even still enjoy it.
You should be proud of yourself!
Oh my god, I'm stduying for my final algorithms design class and this video is just perfect even for people not in to CS
I know its been 6 years but i keep coming back to this. Please make more!
I keep coming back to this awesome video for the background music. Would appreciate a captain's help right now!
you just explained my whole semester of Intelligent Systems in one video.....wish i had seen it before the exams..😜
I've got a quick way to play sudoku: Press the "hint" button. I'll take my prize money in non-sequential 20's, please.
+Sean McKinley I can't tell if you didn't watch the video, or if you just thought this was still witty in spite of it.
NoriMori Yes
+Sean McKinley Okay, _that_ was actually pretty funny.
+OmnipotentDemigod I like the cut of your jib. Protein misfolding is the key to so many of our diseases and interests me incredibly. I'm of the belief that protein misfolding diseases are a natural consequence of our living longer lives than any other time in human history, and to be able to "hack" our cells into preventing this from occurring would be nothing short of a miracle. As an APO E4 allele carrier, I sure wish we had that hint button.
+Amy Ortiz What is APO E4 allele? (I could look it up, but that is usually less interesting than hearing it from a person.)
This makes me cry everytime I see it. Hope you can come back with these or anything else at all
This is the single best explanation about p-np that i could ever ask for... you explained this a lot better then my books... Thank you!
Solving why Hackerdashery made two utterly amazing videos and then promptly disappeared is an NP problem.
What a beautiful video. Thank you for making this.
If I had seen this 4 years ago, I probably would have become a CS/Math major rather than EE/Physics. Oh well, that's another life for somebody else.
Thanks again!
Also, thank you for providing me with affirmation that math terminology is largely unhelpful. It feels great to know that others agree.
I am just amazed by the style of explanation. Terrific
Excellent explanation and coverage with examples. Thank you.
Imagine being so good at sudoku that you cure cancer
8:00 That is where my head starts hurting
The video thats a gem with no BS and engaging. Still watching in 2022.
This was a brilliant piece of work.
P=NP
Divide by P
N=1
Give me my million dollars.
Mutantcy1992 Now you have to solve for P.
Rooket6 P is defined, so problem solved.
Mutantcy1992 I'll give you that one. P = NP CONFIRMED!
Divided by a variable. Error in proof. >|
Yumita kun P is a known set. It can be divided >
P Vs NP is an “NP problem” and since you can’t solve an NP problem efficiently without a NP solution... you can’t solve p vs np efficiently in its current framing.
If anyone can reframe the problem in a way we can get a solution to, it can be solved.
We are currently stuck in circular reasoning in p vs np and that mental block is the same flaw that computer programmers are stuck in when they try to write a sodoku solver.
It may be something about our mental wiring or how we perceive time itself that has an actual blind spot in our thinking and we effectively need a paradigm shift.
Mandela Effect Comedy i can describe it by ten words,then computer can slove anysize sodoku.
No its not, P vs NP has no answer, and even if it had it isnt something we can compute, nor simplificate. P vs NP is merely the question "can complicated processes be simplified to a logic so simple it matches multiplication?".
If there is an solution. I would say it would be a way of calculating what answers there probably are. Checking wich one is right would be an P problem...
This video is one of many things that sparked my love and interest for theoretical computer science and mathematical logic.
I keep coming back here, its magical