P vs. NP - The Biggest Unsolved Problem in Computer Science
Vložit
- čas přidán 20. 01. 2020
- Get a free audiobook and a 30-day trial of Audible (and support this channel) at www.audible.com/upandatom or text "upandatom" to 500 500 on your phone.
Hi! I'm Jade. If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
Subscribe to Up and Atom for physics, math and computer science videos!
/ upandatom
Visit the Up and Atom Store
store.nebula.app/collections/...
Computer Science Playlist
• Computer Science
The Four Color Theorem • The Four Color Theorem...
The Halting Problem • The Halting Problem - ...
Follow me @upndatom
Up and Atom on Twitter: upndatom?lang=en
Up and Atom on Instagram: / upndatom
A big thank you to my AMAZING PATRONS!
Bob, Purple Penguin, Damien J, Gadi Shalom, Chris Flynn, Ofer Mustigman, Mikely Whiplash, Sachin Shenoy, Yana Chernobilsky, Lynn Shackelford, Richard Farrer, Adam Thornton, Dag-Erling Smørgrav, Andrew Pann, Anne Tan, Joe Court, Brandon Combs, Damien Holloway, Ayan Doss, Marcus Dentrey, John Lakeman, Jana Christine Saout, Michael Dean, Chris Amaris, Daniel McGown, Matt G, Dafne Kiyui, Broos Nemanic, John Satchell, John Shioli, Todd Loreman, Susan Jones, Lou, Hassan Sedaghat, Alan McNea, S, Daniel Eliassen, Sam Ross, Julian Engel, Shawn, Israel Shirk, Kay, Peter Walsh, Osa and Beth Fitch, Garrett Chomka, Jeff Schwarz, Josh B, Zach Tinawi, Bernard Wei, Bobby Butler, Matt Harden, Rebecca Lashua, Pat Gunn, George Fletcher, Jasper Capel, Luc Ritchie, Elze Kool, Aditya Anantharaman, Frédéric Junod, Vincent Seguin, Paul Bryan, Michael Brunolli, Ken Takahashi, Jesse Clark, Steven Wheeler, Atila Pires dos Santos, Roger Johnson, Philip Freeman, Bogdan Morosanu, KhAnubis, Jareth Arnold, Simon Barker, Shawn Patrick James Kirby, Simon Tobar, Dennis Haupt, Renato Pereira, Simon Dargaville, and Magesh.
For a one time donation, head over to my PayPal :) www.paypal.me/upandatomshows
Animations
Tom Groenestyn
Music
Epidemic Sound - Věda a technologie
Ahh guys I mistyped the audible link at 14:41! It should be audible.com/upandatom
Sorry for any confusion!
"sorry for any confusion" gees is that all you Sydney girls know how to say or what *joking dont shoot me
@@artdodger5053 look mate
One more typo at 7:35!
"A set-by-step argument"
Up and Atom Jade, can you please make a video about the Dirac equation and antimatter?
@@mohammedkhan4990 I want to make one about the Dirac equation but I need to understand it first!
I loved the 'family to feed'
I always get the biggest kick out of seeing one of my favorite youtubers comment on the video from another favorite youtuber. And, shouldn't you be watching these videos on Neblua? :P
...
There must be many great channels that I don’t know of. I wish Medlife Crisis would make another video of what other science related channels (other than medical topic that is already made and greatly appreciated)
I saw your family at 7:50 lol
Kitties!
@@CChrisS217 I noticed it came out at the words "candy crush".
14:12, “One of the first books I read was ‘Algorithms to Live By’”... I think one of the first books I read was “ The Very Hungry Caterpillar”.
It's called context.
The first book I read was Walk About was I was eight or nine years of age.
And that's why you're not a CZcamsr.
I'm pretty sure this wasn't the first book she read since it was published four years ago lol
Mine was titled "Chicken Licken"
“But before I tell you about that let me tell you about..”
* raises thumb to start skipping*
“What would happen if P DID equal NP”
*whew*
@@DarkKnightCookies Not only that, she managed to avoid mentioning audible or skillshare
6:41
Does anyone know what a gauss is at 7:35? Really appreciate it
@@kutsy3785 she did mention audible tho at the end?
@@HassanAhmed-rf9xr Gauss is a very famous and accomplished mathematician. She is saying that if P is equal to NP, that would mean that any person who can understand basic logical steps would be equal to Gauss.
13:05 It can also mean that the problem was misclasified as NP. Similar thing happened with solving LP problems. The Ellipsoid Algorithm for Linear Programming gave a P solution to what was earlier considered as NP.
If the problem is trully np complete then no, it is the nondeterministicness itself that we would be attempting to make deterministic
Non-deterministic as initially qualified. By using genetic algorithms, etc, does close enough ultimately and practically approach determinism?
@@bitwise2832 define genetic algorithm, do you mean algorithms already present in our genetics or are you saying moreso an algorithm discovered by evolution or an evolutionary algorithm itself? Im far from an expert on P vs NP but id say that NP problems can be tackled with evolutionary algorithms and the algorithms discovered by said algorithm (im not entirely sure if those algorithms can be pulled from the machine after the network evolved them, though I do think that this would be very fruitful)
But these dont prove P = NP, just that you can more efficiently find solutions, it has to be a deterministic solution i.e. this solution for this specific instance there are 42 moves to solve.
Thats my interpretation of what I read on wiki, but didnt realize that the N stood for non-determinism until i read wiki? I cant remember I didnt rewatch the vid.
I preferred the n^2 vs 2^n explanation but find it hard to see why 2^n is non deterministic and not just very large?
Either way its more so a definite solution as opposed to an approximate one, in the natural world there tend to be multiple solutions to the same problem, all seem to be better or worse than each other but are only obvious after evolutionary time, If P = NP and evolution could use that perse then this wouldn't be the case?, however, perhaps there are greater basal calculations taking place that we can't see...
Do you know what nash equilibrium is? I havent thought about this but id be interested to see which proportions of the nash are P and which arent so obvious...
@@cabudagavin3896 GA is described here. en.wikipedia.org/wiki/Genetic_algorithm I recall using GAs in my grad program, a class in Decision Support and Expert Systems. After perusing the wiki article I now recall many of the limitations. However, I was quite impressed (I am easily impressed) at the power, sophistication and "good" enough optimized results in a resource constrained universe, in addressing train scheduling, travelling salesman, and other problems. My day job is much more mundane, coding simplistic business support systems. 🙂
@@johnchufar1571 good cite, I dont suppose you have any good literature on DSS and ES? and what are some limitations of genetic algorithms that you have found to be particularly glaring? If you dont mind me asking...
At first, this seems like a P problem but when it's explained by an insightful teacher, my brain starts having NP thoughts about it. Thanks for making my Tuesday awesome!
you're welcome uncle Mike!
Yeah sure get a recommendation from your Uncle! My mum thinks I'm genius too!
@@klam77 😂
@@upandatom he's just 10 yrs older than you 😠why called him uncle😭
@@klam77 So? Is you mom right or what?
As a nerdy rapper once said, "if I could factor large composites in poly time, I’d have enough money to not have to rhyme."
lmao who said that?
@@SuperFloraLP I found out: The song is called Alice and Bob by Mc+ Plus
It's about cryptography and the rapper is sadly not on Spotify
@@lucagerhardt9839 oh my god that is a treasure thanks bro
@@SuperFloraLP "I showed it to your mom and she used Hoare semantics" 😂
I can appreciate the incredible and enourmous summarizing, communicating and teaching efforts underlying this video. It's REALLY well done!
Same. This is one of the best produced, in terms of engagement and accessibility, videos I've watched.
@@jokii6655 totally agree
You’re in a league of your own, jade. you have the incredible ability of saying all the relevant things about a topic, nothing less and nothing more. Great video
Great video, but there are a few points I would like to make as this is an area I know a bit about:
First off, the complexity of an algorithm has nothing to do with how long it is to write down or how complicated it is to follow. It is merely a measure of how many steps it will need to take. This is a very important distinction that many don't get when they come in contact with complexity theory for the first time (I don't think you did but the way you worded it might mislead a few viewers).
Second, the contrast to polynomial doesn't have to be exponential. There is a large class of functions that are both superpolynomial (so an algorithm would not be in P) but also sub-exponential.
And third, it's important to make the distinction from optimization problems to decision problems. P and NP concern decision problems, so Traveling Salesman, Scheduling etc. are not really "in P" or "in NP", only their decision counterparts (can we find a salesman route shorter than x or not?) are.
Fourth, it is important to note the fact that even if P=NP, we might not be able to ever solve any "former" NP problem in any reasonable amount of time, as the constants arising from the conversion might be astronomically huge.
Last, I also think NP-complete needed a bit of more explanation: The crucial part about NP-completeness is that any NP problem can be reduced to them, so if they would be solvable polynomially, all of the NP problems would be.
@@steak8278 I don't know by heart whether this problem is NP-complete. If it were, solving it in polynomial time would indeed solve P=NP. Polynomial is an asymptotic term though. It means that for some c large enough but constant, for large n your runtime will always be less than n^c. Therefore solving any fixed size problem won't prove that it is in P. It might give you good insights on the problem and give you ideas on how to solve it though!
the way i understood it... is that proving P=NP would bring a LOT more impetus to rigorously develop algorithms for NP-complete problems - because these new algorithms would enhance efficiency by SO MUCH that it is worth every minute of hard labour finding them. however, if P=/=NP, then any effort expended into searching for those monumental algorithms would've been utterly futile.
not sure if that's the correct conclusion, just what i arrived at.
@@steak8278 The partition problem is usually solvable in practice, because the vast majority of cases in the partition problem are "easy cases" where you can pick out an answer(or prove that there is no answer). It is still not NP-Complete because there are some very bad worst cases. A problem is only part of P if for any input (including worst cases) the algorithm will result in an answer after performing a number of operations that is a polynomial function of the number of the size of the input. The interesting reductions where you solve one NP Problem using the solution to an NP-Complete Problem tend to involve the WORST CASES of the NP-Complete problem, so the fact that as a practical matter you can usually solve partition problem questions quickly doesn't help you.
Not quite - If it is proven (or not proven either way) that P != NP, (P =/=, using your symbology), then we *Still* get payoffs in improving known NP problems (with better algorithms), because it can drastically reduce the CPU time, and potentially (this really depends on many factors though, like memoization) reduce the space complexity of the algorithm - IE, how much RAM do we need to solve it (ish).
If P != NP, there is still a rich world of NP problems to solve with major payoffs, simply by shaving away at inefficiencies and improving calculations of specific processes.
@@steak8278 if you consider each interaction of force carrying particles as a "step" in the process used by the universe, every problem that is "solved" by the universe on the macro scale is exponential. And if every change which takes more than a plank length to happen in a field in QFT is a "step" then even quantum problems are exponential. I'm not sure this is relevant to computer science, unless you have some suggestion for a new kind of computer which can take better advantage of the fundamental forces of nature to process data than what currently exists.
I shouldn't watch this whilst high.
i was re-watching one of my favorite series when I was a teen Numb3rs, and got curious when the main character talked about P vs NP and ended on this video! amazing work
Small mistake: The runtime of the sorting algorithm @10:02 is not 200 steps for 100 inputs but rather around 100 * log_2(100) = 580 (the logarithm is always for a base of 2, in computerscience anyway ;D )
Small mistake:
100 * log_2(100) = 664
NERD :)
"Why is this question a question?" is a fantastic question!
Q: why is, "why is this question a question?" a fantastic question?
A: even a puddle of flea piss seems DEEP to a pretentious simpleton.
@ikrinjah - only a fool would infer that I cannot or did not answer the "question," or that i claimed to be a genius. it does NOT take a genius to recognize weapons-grade baloneyium. all that is required is to NOT be a fool.
"A wise man learns more from a fool's questions, than a fool learns from a wise man's answers." - Bruce Lee
dk6024, excellent! You’ve just answered the question, _’Is _*_”Why is this question a question?”_*_ a fantastic question?’!_ And in the same spirit, I now feel obligated to ask:
_Is 'Is "Why is this question a question?” a fantastic question?’!_ a fantastic question?
Or, more fully:
Since _"Why is this question a question?" is deemed to be a fantastic question, and, further, _'Is "Why is this question a question?” a fantastic question?’_ is deemed, likewise, to be a fantastic question, then is, 'Is "Why is this question a question?” a fantastic question?’ itself a fantastic question? Or even a super-fantastic one? [Drops mic] 😎
Is that a rhetorical question?
I have to strongly disagree to that statement. If we would not try to answer questions that do not immediately seem game changing we would probably still live in caves. There is a famous story of when maxwell was asked by a polititian something like "why should I care about your findings" and he brilliantely answered something like "I do not know what it will be used for, but I am sure you someday will apply taxes to it". Or thinking about black body radiation (doesn't sound very relevant at first glance) lead to the discovery of quantum physics, which is essential for most of our modern technology.
I first heard about this particular problem in a computer science lecture in 1991. It set my mind in a whirl and has never failed to make me occasionally think about it ever since.
New subscriber here! Love your explanation of this problem! I feel your explanation is by far the best I have ever seen! I came upon this watching your 1+1=2 video. I also love you used Rubik's cube as representation to explain what it mean to have a solution to a problem can be quickly verified (a solved cube) but is difficult to solve (your rage attempt against the cube) What's more interesting is rubik's cube was a NP problem turned into a P problem (world record less than 4 seconds) with clever algorithm, which goes to your point at the end of the video!
I came here trying to understand the P v/s NP problem and now I leave searching for the algorithm to find love
Did you find it yet? :)
I have been majored in Computer Science for around 3 years now, and today you made me fall in love with it even more.
There is no such thing as computer science. They call it science, it is not science. Name one thing that unique to computer science. None. I majored computer science too.
@@seanleith5312 hi can I ask whats the most important unsolved problem is computer science. Can you list some?
@@nicw9f, are you real? Am I real?
This video is GOLDEN and easily the best video discussing the complex ideas of the complexity classes with apt analogies - I can't believe it is so underrated.
I just watched this episode and my 7 year old daughter joined in to watch it and was inspired by it (and I'm an IT geek so naturally I'm fascinated by these!) - thankyou so much for producing these! Hopefully we'll watch the rest of them together.
P vs NP: The only winning move is to not play
-My CompSci Theory professor probably
Wargames 1983. Great movie :)
P=NIS
A strange game indeed
After getting sucked into this problem a few years ago, I'm beginning to think this. Several years later I don't know when I should give up.
How about a nice game of chess?
The problems we really need to solve are:
Why is your boss a bipedal wingless chicken and why does your family consist entirely of cats?
I know this is a joke, but for the people who don’t know: if p = np, then it would help us with things like protein folding, which could help is cure cancer. So if you find a quicker way to do sudoku, then it could help us with this problem.
This is what happens when you solve all your problems using algorythms
This is an NP-complete problem.
Behold, her boss is a man
@@captainobvious.29yearsago70 Diogenes boss lol
haven't checked a lot of comments, but the number scrabble game is not just like tic-tac-toe because there are combinations with other than 3 numbers that add up to 15, like 1+2+3+4+5 or 9+6 or 8+7, so these lower digit combinations are way more impactful and worth to go for, as you'ld only need 2 numbers to win, whereas higher combinations need more turn for even a chance to win. Additionally, if the enemy blocks one of your numbers because they understood your plan, you can substitue the second number in your plan for multiple lower ones, which would increase the number of possible winning digits on your part even more.
Tic-Tac-Toe is a nice visual simplification of the game, but disregards the point where the amount of digits can be chosen freely.
Great video! It's really hard to explain to people what P=NP is about -- the question of "why can it be so hard to find a solution if you already know how to verify it easily" is truly a fascinating one for those with inquisitive minds :)
Just want to bring up a minor nit - as somebody who had dabbled in competitive programming many many years ago, I found this to be a bit of an eyesore for me (don't worry it's just me..) At 4:39 - You're off by a factor of a million. For O(n^3) algorithms, n=100 does not take 3 hours. It takes milliseconds. For tight loops in non-interpretted languages on modern machines, n=1000 is a couple seconds. n=10000 probably closer to 3 hours... (I did not check whether the 2^100 runtime estimate is realistic -- the computer would have degraded into dust after a couple million years)
"You fluffed your way through the job interview and don't know much about coding..."
I'm in this video and I don't like it.
@vctjkhme Don't listen to this guy. You are an impostor. Now get in the airlock.
@vctjkhme I've seen people get coding jobs after fluffing the job interview.
That's most of computer science students.
Just came to say this video was fantastic, especially how you opened the subject in the beginning in very simple terms with very simple examples! I’ve been thinking of making content like this, but you have it all under control - I can rest easy knowing I can always share your videos 🙂
Okay! this is the best P vs NP explanation I've seen thus far
I paid a university an obscene amount of money to attend a class where this concept was "taught", and I learned more in your 15 minute video than in at least 4, two hour long lectures. I can't recall the last time I subscribed so fast!
matt it DOES pay you to stay awake in class, late night parties are a 90s thing not 2000+
“You have a family to feed” and then shows a bunch of cats killed me xD
Great video! You left out an important fact about NP, which is that a) every problem in NP can be reduced to an NP-complete problem and b) all NP-complete problems are equivalent, so solving even one NP-complete problem would solve every problem in NP.
(also, P = NP if P = 0 or N = 1)
Very nicely laid out! Appreciate you repeating yourself on the important parts and giving great examples!
This is an awesome explanation, and thought provoking video! Thank you.
From a fellow Aussie, and Comp Sci student :)
Nice video. There's one inaccurate detail though. NP is defined as the class of problems that can be verified in polynomial time as you correctly stated at the beginning and not as the class of problems that can be solved in exponential time which you said later. This latter class is a bigger class usually denoted by EXP that includes both P and NP and is proven to not equal P. But again, overall nice video.
In fact, NP stands for Nondeterministic Polynomial, ie, problems that can be solved in polynomial time by a nondeterministic Turing Machine. But I think it's better to stay away from formal definitions, just to make things easier to understand!
*>"[the class of problems that can be solved in exponential time] is a bigger class usually denoted by EXP that includes both P and NP and is proven to not equal P."*
Then, all that about proving that P=NP would mean that we can easily solve all the hard problems... is incorrect? Isn't most of the video incorrect then?
@@Tomyb15 We will be able to solve all the hard problems that can be verified "easily", and many recurring problems in computer science are in this class, but certainly not all the hard problems are solvable if P=NP.
@@steak8278 yes, but it has to be polynomial in length of input, not the magnitude of the numbers.
@@steak8278 Kindof, but in case of partitioning it actually refers to size of the number, because for this problem, that is the size of the input.
Mathematicians:
If P = NP
There Are 2 Cases
N= 1 Or P = 0
Yes, but in Computer Science, you can have
N = N + 1
ldo17.tumblr.com/post/22356042146/the-equation-that-changed-my-life
@@lawrencedoliveiro9104 Not really. Some languages use '=' for assignment, but it is better written like this:
@@ciarantaaffe5259 I prefer “:=”.
@@ciarantaaffe5259 If you get anxious about using just = for assignment in that same task you can use N += 1; which is used nowhere else as far as I'm aware :P
1*0 equals 0 because "1 times anything equals that thing" or because "zero times anything equals zero"? If i ask "what makes 1*0 equals 0?", how would you answer me?
I came here just to know about the difference bw P and NP problems for my exams but got some interest in this topic after your simplified explanation(P) of this complex concept(NP). Thanks a ton!!
This demonstrates the power of good communication. I am not a complete novice to P=NP but never heard about it that clearly and concisely. Very well done!
Your animations are the visual manifestation of anxiety.
That's so right
Muy distortion shows obsesión in the Cage...
They really remind me of Hannah Hillam's comics
Shhhh before she makes them Viral NFT’s
Great video Jade! So well explained. This was one of the most interesting things I studied in my Comp Sci degree in the early 80's, and still remains a mystery.
Ha .. took a 4 month comp sci course in uni to understand this (albeit at a bit deeper level). Love how you've simplified this for pretty much anyone.
I must say I enjoyed watching this video. You made the classes of computational complexity easy to understand. Thank you.
It’s a treat to see Jade after so long. Great video as usual!!!!
thank you!
I wish your videos about comp sci was around when I was at uni. I would've found these philosophical algorithmic problems so much more interesting. Thank you for reinvigorating my curiosity! Keep the vids coming
1:48 I remember when I first learned how useful that was in proofs like 12 years ago and it changed my entire outlook on life. Oddly enough, it really opened me up to the value of the humanities, in particular.
This is the third P vs NP video I watched and the one that helped me understand the most. Thanks!
Thank you for this video! You explained things in a digestible way. Also "algorithms to live by" is such a great book recommendation!
Thanks for explaining P vs NP. I first heard of this problem on an episode of Elementary. Your video filled in the gaps very nicely.
Thank you for helping all of us to understand. I really appreciate how in depth you go. It's hard to explain, but thank you so much. ROCK ON!!
At nine minutes you described the "shell sort," which I used all the time during my programming career. Many people asked me how to become a programmer, so the first thing I suggested was to find a way to sort a list of items as quickly as possible. Sadly most of them didn't even arrive at the laborious and repetitive adjacent-pair method, so they all thought I must be some kind of genius, which I am certainly not but who was I to argue with them?
The sort at 9 minutes is actually a merge sort - you keep breaking down until you get to size 1, then merge. Unfortunately, the explanation also has a bug.
After breaking down to size 1, 11 and 4 are sorted into (4,11). The next pair is (9,20). When Jade goes to merge the two pairs, she says "takes a look at neighboring pairs and compares the lower numbers with each other, sorts them, yielding (4,9), then compares the higher numbers with each other and sorts them, yielding (11,20). For her example this works.
Imagine if, instead of 11, the first number is 5. Then you'd get (4,5) and (9,20). The merge her way would give you (4,9,5,20), which is wrong.
The actual procedure is "compare the first number of each pair (4 and 9) and pick the lower one (4). Then since you took a number from the first pair, compare the remaining number from the first comparison (9) with the next number from the first pair (5). You take 5 and the list is now (4,5). Since no more items are left in the first list, you copy all the rest of the second list onto the end, giving you (4,5,9,20). If there had been a 3rd number in the first list, you would have compared 9 with that.
Basically, when you take an item from one list, compare the other list to the next item in the list you removed from. Move the "list pointers" down the list until one runs out and copy the remaining items from the other list to the result.
The Genuine enthusiasm makes this more interesting. One of the best videos that youtube recommended. Great Content.
3:44 that scared me god my headphones were on high volume
lol whoops sorry!
@@upandatom Hey! a reply wow! btw, did you change your camera or something? I don't know what it is, but the video looks different
@@SoumilSahu yeah I rendered it in after effects instead of premiere so it went a bit jittery for some reason. Never again! lol
I was dying of laughter there
I’m no mathematician or computer scientist, but just flicking through these videos shows the amazing education out there. What a fascinating problem, and solving it would provide a cure for cancer. How wonderful?
Nice video! 👍 There’s an elegant connection between logic and computational complexity, an area called “descriptive complexity.” A seminal result in this area is Fagin’s Theorem (named after the computer scientist Ronald Fagin): A graph-theoretic computational problem is in NP if and only if it can be expressed in existential second-order logic. There are numerous logical characterizations for complexity classes, including the class P.
I love that Daddy Cool is playing in the background.
Thank you, I finally feel like I understand it!
You do a great job of explaining a topic.
This was such a good video. You explained this great and made it very interesting to watch. Thanks a lot!
Just AWESOME explanation, beautiful! My university have a lot to learn with you about how to teach something.. Subscribed forever
"You fluffed your way through the interview." "... but by being clever and a little scared...."
oof
WOW, This is the single best P vs. NP explanation I've ever heard (and unfortunately, I've heard a bunch that haven't made half as much sense). Thank you!
Totally agree
Excellent explanation! I never really paid attention to this during my maths classes at university. Now I wish I had. Finally I understand the problem and the ramifications if it is solvable.
Somehow we need to find the log of NP problems. So a P^N problem becomes an Nlog(P) problem.
I have been looking for videos to understand NP problems from many time, I stuck across this one and I haven't been this satisfied with a video. You definitely explained it so well and clear. Thank you that this video is in existence. Fully satisfied.
7:48 KITTY!
7:48 [enter jump cut kitty]
I LOVE this video!!! I know this particular subject has very little to do with the complexity of problems, and more to do with creativity, but I'd suggest to google LEGO logic gates. Lots of people have built their own versions of MECHANICAL logic gates (for instance: two inputs may be 2 gears you spin one way, or two shafts you press inward, and the output is a gear or shaft that rotates/moves based on the input and follows that logic).
But with a creative as you are, maybe you could design your own and find a way to connect them. Several problems would have to be solved with mechanical gates: alignment (one gate's output affecting another's input, etc...), uniformity of input/output type, and how to actually make them work... Those are a few examples.
Anyway, I think that would be a very nice subject where, not only could you show the viability of actually coming up with ideas yourself by being creative and putting them into mechanical reality, but it would also show how the idea of "computing machines" themselves (like Babbage's) could have actually been made from mechanical parts.
that's actually a really cool idea for a video...
@@upandatom Thank you.
can't say no to legos or gears!!
@@alveolate Absolutely!
Thank you so much for this video. I'm a student of Mathematics in Spain and that really helped me understand or have a better idea about what NP problems are. Wish the best!
great video. Would love a more detailed explanation of how all NP-complete problems can be reduced to the same problem. The number-scrabble/tic-tac-toe is a great example of how 1 particular problem can be reduced to one particular other problem, but how are ALL the NP-complete problems reducible in this way, and how do we know it?
10:00 log in this case is base 2, it shows how many splits you'll have to make, so the sorting would take about 660 steps, not 200.
my bad
Isn't the notation of n.log(n) already done away with all constants since its just approximation? So unless it's actually equal to n.log(n) base 2 isn't anymore accurate than base 10,
At least according to my current understanding
@@mbrusyda9437 You're completely right ! I think that actually we can bound the number of operations of Merge Sort (the algorithm presented in the video) by 2.n.log(n) with the log being in base 2, but I'm not completely sure. Otherwise, indeed, all the complexities are usually given up to a (constant) multiplicative factor.
@@mbrusyda9437 , Right. Complexity analysis is relatively poor for many practical problems sizes because modern CPUs are superscalar pipelined designs with highly variable memory access latencies and throughput. This makes it possible that in a practical sorting case merge sort and quick sort are slower than insertion sort. But you don't have to pay attention for those details if you just use a good library for your programing language which optimizes relevant cases correctly.
@@mbrusyda9437 The point is not showing the exact number of steps, but how it scales (for large n). And then it becomes clear that factors are pointless. If you have an O(n) algorithm, it'll take approximately twice as long when the input set is twice as large, for large enough n. This is still the case when the algorithm would be O(2n) or O(24352n), so that constant multiplier can be discarded.
Same goes for smaller terms. For example, the n^3 part in an O(n^3 + n^2) algorithm dominates for large n. In other words, if f(n)=n^3+n^2, then f(2n)/f(n)≈8 for very large n. So the extra n^2 part is usually left out.
7:48 - non-deterministic polynomial kitty!
That's one of the reasons why I am majoring Mathematics and Computer Engineering degrees, they overlap in significant points and compliment each other with their list of subjects - especially when we are talking about the most theorical and low-level fields.
This is the best explanation video of the P versus NP problem I've ever seen. I'm definitely subscribing to this channel! Keep up the good work.
7:49 Schrodinger's cat appears: "I've proved P=NP"
7:52 Encryption: "Nope. Made a mistake. Back to the litter box."
"You have a family to take care" (cats)
I really identified myself in here!! HAHAHA
You have the best explanations for concepts which would have been taught at graduate and undergraduate courses!! Amazing
This is facinating - great explanation.
I've been waiting for this video for sooo long!!!
[Edited with an update at the bottom]
Something thats never been entirely clear to me is why proving P=NP would change all these things and not merely mean that all these things _could_ be changed.
I assume that the proof would offer some insight in to breaking encryption or what have you but would a proof necessarily have the power to break open every NP problem there is? and why?
There seems to always be this assumption that that would be the case, that should P=NP we will just have polynomial time solutions to everything popping out everywhere, and Ive never really understood on what basis that assumption is made.
Edit: Some excellent responses below, including ones from KyrSt and Rohit which put me on to: czcams.com/video/XDTOs8MgQfg/video.html A discussion between CS master Knuth speaking with Fridman. (Which in turn led me to en.wikipedia.org/wiki/Robertson-Seymour_theorem most notably the section on Polynomial time recognition.)
A very quick summary of what Im gathering (and corrections would of course be welcome): A constructive proof blows these problems wide open. A non-constructive proof just tells us that an answer exists.
No doubt the latter would spur on a great deal of interest, but to use Fridmans analogy, it could be like a search for alien life. Even if you know its there, it doesnt necessarily mean you can easily find it.
you're right, just because the classes turn out to be equal doesn't imply that we would be able to find an algorithm immediately (non-constructive proofs, anyone?)
it's a hype thing. it always is.
If there's proof that P=NP then *droves* of researchers will start working on polynomial solution to any of the NP-complete problems. And finding polynomial solution to a single NP-complete problem is equivalent to finding polynomial solution to all NP problems since any NP problem can be translated to and from an Np-complete problem in polynomial time.
The thing is, once you do prove you can find a polynomial time solution for any problem, that alone says that any problem you find will have a quick solution. Granted you need to find the solution, but knowing it can be done is a much better situation than not knowing if it's possible at all to get a better solution. Similar to the tic-tac-toe/number scrabble situation, there could even be ways to translate those problems to a previously solved problme, speeding up the process
I guess it kind of assumes that P=NP is proven by constructing a P algorithm for some specific NPC problem. Like Himanshu Sheoran says, once you have a solution for any NPC-problem, you can convert all other NP problems to it. (You prove that a problem x is NPC in the first place by giving an polynomial-time algorithm that "reduces" another NPC problem (e.g. 3-SAT) to x.)
Technically, we might find a non-constructive proof that P=NP, which doesn't include an algorithm for solving any specific NPC problem, or reducing it to a P problem. But it would still mean that such algorithms exist for every single NP problem, and I'd expect it to be only a matter of time before an algorithm for one specific NPC problem gets found - which, again, can then also be used to solve any other problem in NP.
You are right. The proof doesn't necessarily have to give an algorithm for any NP problem. You can search Donald knuth talking about it. But many people currently believe p=/= np. So they try to stay away from it or otherwise there is a chance there life will go wasted. Everyone one will be trying to find an algorithm and the probability of finding one will increase massively.
Exemplary overview and explanation of probably (after Riemann Hypothesis) the most important math question too, P vs NP, wonderful, by far the best I have seen over the years.
P vs NP seems more important than RH. In the sense that RH does not say much about computation. But if RH can be either proven or disproven, then it is an NP problem, since a proof or disproof can be checked easily. So if we knew NP = P, then we can easily discover a proof or disproof. It leaves the case when RH happens to be undecidable, which means that it falls subject to Turing's halting theorem.
wow..one of the nicely explained videos on NP problems. Thank you!
9:32
Bubble Sort(O(n^2))
Merge Sort(O(nlogn))
6:13 - "It's not a pretty picture. I don't like doing it!"
wow you are really good at introducing this deep topics in a clear way! the way you reason seems to me very similar to the way I think, so I feel rrally comfortable following your explanations
In the Analysis of Algorothm class, during the semester I just try to teach the kids to understand the gist of this shairing. Thanks for the summary.
The "Salad Fingers" animation and sound reminded me that Salad Fingers exists and I'm no longer comfortable being in the same planet as it.
Lol two whole afternoons.... I spent 3 years trying to find an algorithm for the n-queens P vs NP problem. :(
haha aww
I thought n-queens was already solved? I was working on an answer for this a while back, but I thought I saw that it had been solved already and stopped.
P=NIS
If you have that, you're not a queen.
@@thereaction18 Solved.
I brute forced it by iterating through all possible board states. So yeah, an exponential time algorithm. Very fast for small values of n though! :p
That's the first explanation of this problem I've understood. Thank you soooo much.
Thank u for the book recommendation! I think I am going to love it . And , you explain hard stuffs so well . I look up to you ❤
For the 15 game, I realized the opponent would always block you if you were close to getting 15. So the only way to win would be to have two ways to win at the same time, so they can't block both. That reminded me of the strategy in tic-tac-toe, and then I suddenly had the revelation that this game is basically tic-tac-toe played on a magic square. Which means any game between logical players will always end in a draw.
Tons of thanks for the two whole evenings you spent googling for this answer and came out with this exceptionally good representation. Your effort is Adorable. The graffiti used for Machine Learning is amazing!
P=PH. rainbow tables for 3-SAT in the delta of the DTM. I put an Oracle in the transition table. Bada bing bada boom
@@Freshiefunnies ?
this was explained so beautifully, thank you so much for the incredible work!
I ran into this problem when I was an undergraduate student at IIT. I am still working on these problems. You did a great job in explaining this problem better than my professor.
Which IIT?
Posting @1:27 on this video: on the "1 to 9" game, my thought process went like this:
15 is an odd number. Two evens add up to even, and two odds add up to even, so no use. But an odd + an even = an odd. So you need both to win, and there are more odds than evens by 5 to 4.. Ego, I somehow decided that being able to pick odds first was advantageous. Then when I advanced the vid a bit (cheater!) and saw the naughts and crosses comparison. I figured, in N&C if you go first and play the right strategy (algorithm) you can't lose. You can't guarantee that you'll win, but you can guarantee that you won't lose. This is because by going first you have potential access to five squares, i.e. you can select all the 'odds' you want (until you need an 'even') and always block your opponent from getting an 'odd' or an 'even' if that's what they need. So go first and play the right strategy and you can't lose, and you might win.
So I hope it's now very clear to you all that ... well, I know how to play naughts and crosses. Seriously, I've got nothing.
nice insight in odds and evens
just one thing in your favor: 3 odds adds up to odd, while 3 evens adds up to even so you absolutely need an odd but not neccesarily an even
-heck two odds and one even adds up to even-
actually, regarding the tictactoe solution... i'm not sure that there is only one magic square for all combinations of triplets that add to 15. are there only 8 triplets that add to 15? i gave it a cursory look-over and couldn't come up with any triplets beyond the 8 in the magic square (3 rows, 3 columns and 2 diagonals). best i could do is notice that the pairs that add to 15 were definitely excluded from consideration.
Nice insight into solving tick tack toe by reverse engineering from a seemingly more complicated problem, That was very unexpected
This is one of my favorite channels along with 3Blue1Brown..
You guys would make an amazing scientific duo XD
2Blue1Brown did a video with Matt Parker, The Australian Mathematician, so it's certainly possible!
At 3:33 you say "the number of steps the algorithm needs to take is proportional to the input size"
A linear relationship is usually denoted by proportional however you are discussing the class of polynomials, which is a strict superset of a linear relationship. I would recommend using a different phrase there, for example "The number of steps the algorithm needs to take is proportional to a polynomial of the input size," or "... needs to take is a polynomial function of the input size."
Excellent video!
The Merge sort demonstration is awesome!!
Jade, I learned this in school over 30 years ago. You just summarized a complete semester for me in 15-minutes!! You rock.
I was very impressed this is one of the good ones a little while( always have a Love ❤️
This video is fantastic. I laughed out loud several times and learned a bunch. Thank you!!
Very well done, kudos. It's a the right level with engaging and funny illustrations.
Thank you Jade.. I am an engineer and use simulation and evolution algorithms to optimise system performance. Models that have no analytical solution have to be run many times for each case and averaged and I found they always plot a straight line on a log - linear chart. Because of that I could write an efficiency function for optimised selection and compare different models by the slope of the line. Doing that for the parameters for evolution of DNA I found I could falsify the theory of evolution by natural selection by showing any model with greater efficiency than the natural case could not evolve a single gene in the age of the planet. Which is the same result Fred Hoyle found and wrote about in _"Mathematics of evolution."_
I think I know what you mean haha
"You've got a family(of cats) to feed" XD
Nice video. I actually listened to that audiobook some years ago. It's a good one.
Recently discovered this channel amazing video u made some very hard lectures very easy and intuitive to understand thanku love the content :)