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

Hi! I'm Jade. If you'd like to consider supporting Up and Atom, head over to my Patreon page :)

Subscribe to Up and Atom for physics, math and computer science videos!

Visit the Up and Atom Store

Computer Science Playlist

*Follow me* @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.

*Animations*
Tom Groenestyn

*Music*
Epidemic Sound

[upandatom]

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

[MedlifeCrisis]

I loved the 'family to feed'

[bartrupel]

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

[HRKnight]

“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*

[gustavom]

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

[Uncle-Mike]

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!

[SingularityLabsAI]

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.

[francescob.]

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

[MrNacknime]

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.

[tstodgell]

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

[goodieshoes]

I shouldn't watch this whilst high.

[richard]

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!

[Psyychopatt]

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 )

[mushiri]

I have been majored in Computer Science for around 3 years now, and today you made me fall in love with it even more.

[malectric]

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.

[sydneyfong]

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)

[dk]

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

[SebastianLopez-kijx]

I came here trying to understand the P v/s NP problem and now I leave searching for the algorithm to find love

[alungiletshangela]

Okay! this is the best P vs NP explanation I've seen thus far

[HerrSurIix]

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.