P vs. NP - The Biggest Unsolved Problem in Computer Science

Ahh guys I mistyped the audible link at 14:41! It should be audible.com/upandatom Sorry for any confusion!

I loved the 'family to feed'

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”.

“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

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.

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!

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.

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

I can appreciate the incredible and enourmous summarizing, communicating and teaching efforts underlying this video. It's REALLY well done!

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 )

"Why is this question a question?" is a fantastic question!

I shouldn't watch this whilst high.

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.

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."

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.

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

“You have a family to feed” and then shows a bunch of cats killed me xD

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?

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.