NP-COMPLETENESS - The Secret Link Between Thousands of Unsolved Math Problems

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

Visit the Up and Atom store

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

*Videos Mentioned*
Deep dives into the Cook-Levin Theorem

*Sources and Further Reading*
The complexity of theorem proving procedures - Stephen Cook
Universal search problems - Leonid Levin
Reducibility Among Combinatorial Problems - Richard Karp
The Nature of Computation - Christopher Moore

*A big thank you to my AMAZING PATRONS!*
Jonathan Koppelman, Michael Seydel, Cy 'kkm' K'Nelson, Thorsten Auth, Tim Barnard, AndrewA, Izzy Ca, Millennial Glacier, Richard O McEwen Jr, Scott Ready, John H. Austin, Jr., Brian Wilkins, Thomas V Lohmeier, David Johnston, Thomas Krause, Lynn Shackelford, Ave Eva Thornton,
Andrew Pann, Anne Tan, Larry Nixon, Ben Mitchell, Steve Archer, Luna Sophia, Viktor Lazarevich, Keith Lazarus, Tyler Simms, Michael Geer, James Mahoney, Jim Felich, Fabio Manzini, Jeremy, Sam Richardson, Robin High, KiYun Roe, DONALD McLeod, Ron Hochsprung, Aria Bend, James Matheson, Kevin Anderson, Alexander230, Tim Ludwig, Alexander Del Toro Barba, Justin Smith, A. Duncan, Mark Littlehale, Tony T Flores, Dagmawi Elehu, Jeffrey Smith, Alex Hackman, bpatb, Joel Becane, Paul Barclay, 12tone, Sergey Ten, Damien Holloway, John Lakeman, Jana Christine Saout, Jeff Schwarz, Yana Chernobilsky, Louis Mashado, Michael Dean, Chris Amaris, Matt G, Dag-Erling Smørgrav, John Shioli, Todd Loreman, Susan Jones, Kent Arimura, Phillip Rhodes, Michael Nugent, James N Smith, Roland Gibson, Joe McTee, Dean Fantastic, Bernard Pang, Oleg Dats, Max Isenholt, John Spalding, Simon J. Dodd, Tang Chun, Michelle, Richard Vallender, William Toffey, Michel Speiser, Rigid Designator, James Horsley, Craig Tumblison, Cameron Tacklind, 之元 丁, Kevin Chi, Paul Blanchard, Lance Ahmu, Tim Cheseborough, Markus Lindström, Steve Watson, Midnight Skeptic, Dexter Scott, Potch, Indrajeet Sagar, Markus Herrmann (trekkie22), Gil Chesterton, Alipasha Sadri, Pablo de Caffe, Taylor Hornby, Mark Fisher, Colin Byrne, Nick H, Jesper de Jong, Loren Hart, Sofia Fredriksson, Phat Hoang, Spuddy, Sascha Bohemia, tesseract, Stephen Britt, KG, Hansjuerg Widmer, John Sigwald, O C, Carlos Gonzalez, Res, Thomas Kägi, James Palermo, Chris Teubert, Fran, Robert J Frey, Wolfgang Ripken, Jeremy Bowkett, Vincent Karpinski, Nicolas Frias, Louis M, kadhonn, Moose Thompson, Rick DeWitt, Andrew, Pedro Paulo Vezza Campos, S, Rebecca Lashua, Pat Gunn, George Fletcher, RobF, Vincent Seguin, Shawn, Israel Shirk, Jesse Clark, Steven Wheeler, Philip Freeman, Jareth Arnold, Simon Barker, Lou, and Simon Dargaville.

Creator - Jade Tan-Holmes
Script - Jade Tan-Holmes and Simon Mackenzie
Guest Speakers - Simon Mackenzie and Matjaz Leonardis
Animations - Tom Greonestyn
Sound Effects - Standard Productions

[personwritingthings]

Jesus I've just gotta say this. I've tried and failed to understand the P = NP problem for literally years, almost a decade. I'm a biologist, so I never really had the time or mental tools to understand the various sources that tried to explain it in an accessible way. Jade, this is the FIRST time I feel like I actually understand the problem. You have an amazing talent, and I'll forever be grateful to Tom Scott for introducing me to your channel. Thank you!

[YoungGandalf]

The Clique Problem is easy to solve in my case, as it's just a single point.

[atmly]

I'm a software architect who has been programming for 30 years and this is one of the clearest explanations of P=NP that I have ever encountered.

[Letsamplay]

This is genuinely the first time I've even come close to understanding P=NP. And I've tried many times! Your way of communicating complex problems is really something special.

[hunternelson]

Truly one of the most amazing videos I've ever seen on YouTube. Out of all the videos I've seen trying to explain NP completeness, this is in a league of it's own for clarity and engagement. It's so good.

[victorcoscrato]

I got to say, as a CS PhD, this video is so well made and interesting that it could easily substitute the first module of any constrained programming course with ease. Very well done

[lvmbk]

One of, if not the, best video you've ever done.
Best compliments for such great passion and dedication. You do not flood the tube with many videos and this is the reason: quality needs time.

[rafaelcpatrao]

This reminded me a lot about my Master's thesis on bi-level, optimisation. In any other case it would be a slightly traumatic experience, but since is Jade doing so in her typical amazing way, it was a joy to watch! Thanks and keep with the great work, I need to go back to my NP-hard problem now haha.

[SimonLanghof]

Digging through the haystack and getting half of it in your hair for a few seconds in the final video - that's dedication.
The video really filled some knowledge gaps and glued the details together for me.

[tomasstana]

As someone with deep passion for computational complexity (and someone who actually studied it in depth), I had the honor to truly undertand what P vs NP is about and more importantly, how fundamental that question is. And adding that it also is quite popular, it left me wondering, why no one on youtube made a solid video about it. If I had time, video editing and presentation skills, I would be making videos about it all the time :D.

Anyway, I am really glad to see a video diving relatively deep into the topic. And I think you've done quite well the balancing of two opposing aspects of this problem - keeping the necessary technical details at minimum while staying true to the essence of the issue 💪💪👍👍.

[charllandsberg]

"So did we just solve the clique problem? <hairwhip, camera 2> No <back to camera 1> continues..." LOL! This was the best moment of all of Youtube this week. Thanks for an awesome video <3

[torsten_dev]

Nice.
We didn't prove the NP-completeness of SAT in our CS lecture so I always wondered how they proved it.
This video gave me enough of an idea on how they did it to no longer wonder about that and be happy to just reduce problems.

[Pingviinimursu]

Phenomenal job Jade. For so long I've known that the NP stuff is something very complex and likely impossible, so I haven't even looked into it that much. Someone explained some of it to me, but I didn't really grasp it. You did a perfect job. Mentioning the people behind the discoveries and animating them was a good touch, it makes them feel more real for me, instead of dead names on old papers.

If anyone asks me about this stuff, you can be sure that if I have a satisfactory answer, it's because of you making this video. And if I don't, I know now where to guide them.

Amazing job, I absolutely think you're one of the best if not THE BEST science communicator on YouTube. Thanks so much for doing what you do, and I hope it's fulfilling for you!

[Rijnswaand]

Thank you! I actually studied computer science and this is one of the issues I never really understood until your husband explained it in this video. Thank you very very much for this.

The teachers at my university didn’t have a knack for explaining things in simple terms. They were more interested in using very fancy words to explain this problem to freshmen. Which is why I never understood this.

[wk]

Your P Vs NP video is something I've thought about at least once a week for years. Than you for the the amazing and thought provoking videos.

[Pseudify]

Watching Jade play the zill is mesmerizing. I don’t want to stop looping that sequence. I doubt I will ever hear the end of the NP story. She said she prefers xylography and yarn crafting?! She missed her true calling…

Thank you. As a student I focused on mathematical analysis and never took the time to comprehend (N vs NP). Maybe I thought it was intended purely in the realm of Computer Science. This presentation was thoroughly enjoyable and at least cultivated a respect for it and humbled by the toughness of this millennium problem.

Shout out to all the reinforcements - those guys are awesome.

[markd.]

I remember sitting through Discrete Mathematics and CompSci lectures for the better part of a year getting my head around these topics. Your video crunches it into a perfect introduction. I wish I had seen this video as an introduction 20 years ago! It would have saved me many post-lecture headaches 😁

[davidf]

Albert Einstein famously said that the key to understanding is to make something as simple as possible, and no simpler. You've done that beautifully in this video. You organized the video just enough for it to make sense, and included just enough foreshadowing to help the viewer follow along. You didn't repeat yourself once unnecessarily. You built the explanation up piece by piece.

Extraordinary work. Many of even the most successful and biggest content creators often struggle with this. I could name several that have millions or tens of millions of subscribers who have never succeeded in presenting on a single topic in such an effective manner. At best typically they either do a deep dive that is unbalanced between breadth and depth, or else they oversimplify or undersimplify along the way, utterly losing the cogent coherent thread of connection, insight, and understanding that they purported to be intending to evoke in their audience.

It's as much about what you do say, as about what you don't say. Well done.

[joebaumgart]

This problem actually occurs quite a bit in the popular trading card game Magic The Gathering. Infinite loops are not only possible but are actually game winning strategies. This means the game state must constantly check for these loops on each players playing field with each other.