NP-COMPLETENESS - The Secret Link Between Thousands of Unsolved Math Problems
Vložit
- čas přidán 30. 03. 2023
- Get Nebula using my link for 40% off an annual subscription: go.nebula.tv/upandatom
Watch my exclusive video on the SAT to clique reduction: nebula.tv/videos/upandatom-sa...
Hi! I'm Jade. If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
Visit the Up and Atom store
store.nebula.app/collections/...
Subscribe to Up and Atom for physics, math and computer science videos
/ upandatom
For a one time donation, head over to my PayPal :) www.paypal.me/upandatomshows
Videos Mentioned
Turing Machines • Turing Machines - How ...
P vs NP • P vs. NP - The Biggest...
Deep dives into the Cook-Levin Theorem
• 16. Cook-Levin Theorem
• Cook-Levin Theorem: Fu...
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
Music - epidemicsound.com
Sound Effects - Standard Productions - Věda a technologie
Hi everyone! If you enjoy what we do here at Up and Atom, the best ways to support the creation of more educational videos are to sign up to Nebula with this link go.nebula.tv/upandatom, or to support me on Patreon www.patreon.com/upandatom. Thank you for watching :)
One of the best video on the net.
(In my humble opinion)
Sign up and watch indeed! I’m so glad I did!! Thanks again Jade!!! 👁🎬🎬🎬🎬🎬🌈☮️💟😍🥰😘🚀🌌🗽♾💯🤯🤩🤩🤩…
@@aurelienyonrac 💯♾
I wonder if the answer to this question has to do with finding the shape of a positive configuration, based on the number of nodes required. If you then just could search for the shape rather than testing the connections between nodes, it feels like a logical best place to start as a guess. Though I'm sure I'm oversimplifying this.
Hello Jade. Clique comes from a french word which has both pejorative and military connotations... We're doomed.
The Clique Problem is easy to solve in my case, as it's just a single point.
It's the time it takes, not the actual solving of the problem.
dw Gandalf. I feel you, even if Joe doesn’t.
I’m like that too as of now.
Just wait for Bilbo
@@joebaumgart1146r/whooosh
If anyone asks why i dont go to parties, I'll just send them this video
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!
Aww thank you so much for the kind words :)
If the np approach is really just guessing the entry values it may be easily compared to "solving" lottery. If millions of people apply truely random methods of choosing their numbers, it will be far easier to have someone get the right number. But if all used some brute force method, the input would have far less variation. So parallelization fails.
I’m still fuzzy on something. There is the guessing aspect but there is also the parallel processing of those guesses. I’m not clear on which of these 2 aspects is the important one. Paul Googol seems to be suggesting that the trick is in guessing ALL possible combinations. I don’t understand why that aspect is the challenging part as I would think that you would simply take all possible inputs and randomly combine them as many times as necessary to get all possible combinations.
@@Pseudify what you suggest is brute force. It is hard to parallelize so many computers or users may give their adapted input. You just cause lots of communication traffic. If just random input is chosen, you may just have infinite users giving their guess and just 1 has to be correct.
"Guessing all right combinations" is not the goal as far as I understood. Just one. I guess the bottleneck there is the merhod for creating random input. People doing lottery often use similar patterns and rng has the same problem.
I second Filippo’s comment! On a tangent, the nondeterministic model is very similar to how Prolog programs are executed. But I guess a Prolog program is pretty much just a bunch of predicate logic statements that need to be satisfied, so it’s analogous to the Boolean “sat” examples discussed in this video.
Now you need to do a follow-up video on Prolog! 😂
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.
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.
Truly one of the most amazing videos I've ever seen on CZcams. 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.
thank you :)
I was about to say the same thing!
+1 thank you so much Jade!
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
As a CS BSc Peasant, I don't know why the computation part was not taught. It is the missing link between "Thou shall believe these are equivalence classes and nay varlet, no sensible logic will be provided, just abstract reasoning. Now clap your hands for me monkey."
This video made me finally, retroactively, understand P=NP instead of having to blindly believe in it. Same way Neal Stephenson's Cryptonomicon made me understand the formerly cryptic introduction to AI course, but years too late. Teach me properly, don't make me clap my hands!
@@dirkbester9050 if P equals NP and you know it clap your hands
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.
But it was worth it to find that needle.
@@vigilantcosmicpenguin8721 The purpose of finding a needle in a haystack is not 'to have your needle back' but to be able to feed the hay to your livestock without risk of bodily harm to the animals caused by an ingested needle.
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.
Thank you so much 😊
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.
lucky you
I'm dealing with PSPACE-complete nightmare
That’s neat. It reminded me of my kindergarten thesis.
Slightly traumatic 💀💀💀
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 💪💪👍👍.
what books or software do you use to study that topic?
@@krumpy8259 That depends what you already know a where you aim and how much time and dedication do you have.
TLDR, I do not have anything to recommend, sorry :(.
I had it built piece by piece from many small fragments over a long period of time, most passed to me by professors at the university, and also a lot came from simple thinking (about opened questions, trying to find fast algorithms for SAT problems, even though you are destined to fail, but trying it gives you a lot of insight etc.). So no collection of available sources or courses I'd know about.
Look up "P vs. NP and the Computational Complexity Zoo" on youtube. it is pretty good.
@@krumpy8259 I like the book “introduction to algorithms” because it’s written with Rivest, the R in RSA. That book will explain a ton. However in general you should understand discrete mathematics I.e. sets, graphs, trees, combinatorics and probability. The P = NP problem is deep precisely because it relates seemingly different problems as well as individuating seemingly identical ones.
@@krumpy8259 I recommend two books, 1) Theory of Computation, by Sipser; and 2) Algorithm Design by Kleinberg. Both were assigned to me during my cs degree and they each contain detailed information on the P vs NP problem. You will surely gain true understanding by working through some of their exercises.
"So did we just solve the clique problem? No continues..." LOL! This was the best moment of all of CZcams this week. Thanks for an awesome video
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.
We did that but that class (called Theoretical Computer Science) was just about the only one that was really interesting. I didn’t care that much about Operating Systems and Fuzzy Logic etc.
Also I remember we had some cool DOS software that could throw two dozen different algorithms at a Traveling Salesman Problem and compare their performance, with graphical output showing how each gradually improved its results. Been trying for ages to get hold of a copy…
Did you by any chance study at TUM or elsewhere in Germany?
(comment in reply to @magicmulder)
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 CZcams. Thanks so much for doing what you do, and I hope it's fulfilling for you!
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.
Why is this still a thing? (And i mean in most fields)
@@nyet_maker7948 you mean the usage of very fancy words to explain things to freshmen?
Well first of all I was a freshman in computer science over 20 years ago. I can’t say if that’s still a thing. Even back then some of the younger professors seemed to be more interested in actual teaching and getting their point across than their older colleagues. But certainly not all of them.
Also I believe it has something to do with the fact that in order to teach at a university you just have to be good in your field but not actually a good teacher. You don’t have to study pedagogy or know anything about didactics.
Understanding something and helping others to understand it are two different things.
@@Rijnswaand "Understanding something" is necessary to "helping others to understand it" otherwise end up "helping others to understand wrong things"
@@nyet_maker7948 because you go to a university to learn advanced topics and a lot of that by yourself. a professor is an expert in his field and not a teacher and doesn't care if you understand a term or not. you have the entire knowledge of the world at your fingertips now anyways and can just google what a term means and things will become clear. what's so hard about that?
in first semester math a girl was like "prof. xxx i don't understand this" and he just turned around "and what am i supposed to do about that now?" and went back to the board and his equations. the prof is there to teach you yes but not to make you understand. if you don't get something you work on that in your own time. that's not what classes are for. they tell you what you need to know. how you aquire that knowledge is your own problem.
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.
Did you see the video about MTG being Turing complete? Search for it.
czcams.com/video/pdmODVYPDLA/video.html
Mfw you have to solve the halting problem to win a MTG game.
I haven't played MTG, but if you track each "board state" in a map can't you detect prior moves and avoid repeating them or make a move to thwart your enemies attempts to create a loop? (see the A* algorithm)
When I'm playing 8-ball and have an impossible shot, I'll try to place the cue ball where my opponent will face a shooting position that is at least more difficult than where it is.
MTG is actually turing complete though (there's a paper and YT vid about it) so due to the halting problem, it's impossible in general to determine whether you are in an infinite loop. Though ofc this situation doesn't really come up in normal games.
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.
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.
Thank you so much 🥲
Yes, yes, yes! Everything you said. Thanks for taking the time to write it out!
@@hopegold883 😅🤗
@@upandatom you're welcome! This ability to communicate understanding of a topic to laypeople outside of the field is much more rare I think than the ability to cultivate understanding itself for one's self, and more rare than the ability to teach other individuals. I suspect a lot of people who are good at this like you are divert their efforts more to either research/learning/understanding and/or teaching, which is understandable as those pursuits are fundamentally more productive. So I hope you continue to do this from time to time however focused you become on other endeavors, because while it's not the most productive thing, it's also very rare and creates an opportunity for people to gain a useful understanding of something that they never would otherwise without people like you taking the enormous time and effort it takes to synthesize something like this for them. Thanks!
I am only replying because you said that you haven't found any other channel that explains this stuff as well so you might be missing out on some great creators who specialize in different things (but mostly general science). Ofcourse there will be variations of quality and how easy to approach the stuff is, and this is just my list in no particular order:
- 3blue1brown
- Science Asylum
- Arvin ash
- Aleph 0
- Alpha Pheonix
- Branch Education
- Computerphile
- eigenchris
- Fine Design
- sabine hossenfelder
- How money works
- Joe scott
- Newmind
- Physics Explained
- Robert Miles
- ScienceClic
- Sixty Symbols
- Smarter Everyday
- sudgylacmoe
- Technology connections
- The action lab
- The thought Emporium
This is not an exhaustive list by any means, and I did not add creators focused on more narrow fields like CS, Software development, FOSS, Music theory, mechanics etc.
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 😁
Amazing video, Jade! I can see how much work you put into creating an engaging story and adding some entertaining transitions, and I think it's really paying off in terms of video quality.
The completeness was most interesting (and previously poorly understood) to me, but I can see how many of these problems can be boiled down to a SAT type problem or a Clique problem, where a solution exists if all required Boolean relationships are satisfied.
The best I can think of to simplify the computation is pruning Boolean values that are incompatible with known parts of the solution, and split possible solutions into groups based on which values are mutually incompatible, but that only goes so far and might just reduce some problems to NP problems of smaller order.
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…
2:22 "Clique" is a French word, it's slang for your "group of close friends", ie. the people you click with. "Ramène ta clique" would be "Come and bring your group of close friends". It has to do with the fact that in French too, we say that two people "click" when they immediately like each other, so "your click" would be that group
Isn't it pronounced differently?
@@guidoferri8683 It's really the same prononciation and the same word as "click". We "clique" on a computer mouse, for example
@@ThomasGodart I guess I confused it with cliché
@@guidoferri8683 Maybe! "Cliché" means something like common knowledge, but it's the French word for a camera capture, so supposedly it's something that would be printed on an ad or something, which means that it can be exaggerated
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.
I'm so glad you made this video.
Although I've been a computer scientist for two decades now, and am inclined in the theoretical aspect of things, I never quite knew understood how 3-SAT is NP-complete. Whenever I tried to look it up, people only ever talk about reducing SAT (directly or indirectly) to another problem to prove the other problem's NP-hardness. Never of the NP-hardness of SAT itself.
amazing, you did a great job in explaining it.
especially the parts that didn't click well with me when i studied it in college ( the need for non deterministic model notation )
keep it up( and atom )
Such a co-incidence. I saw your P vs NP video few hours back as a refresher
I could never find such a great vidoe on this topic !!
A huge thanks.
Keep up the fascinating work.
Cheers to Up and Atom :)
Fantastic video, Jade. Love your content.
Not only is this video good , it is NP-good
Thank you for making these videos! I love the posters in the background
I got really interested in P vs NP when watching your other video. So excited with this video!
Non-determinism reminds me of quantum bogosort. Randomly shuffle an array, and check if it is sorted. If it is sorted the algorithm halts. If it is not sorted the algorithm will destroy the universe. Assuming the many-worlds interpretation is true, only universes where the array is sorted will be left. This is of course assuming that the shuffling is truly random. You wouldn't want to accidentally use a shuffle that couldn't produce the sorted state.
lol
Or that the sorted state is not possible. So long, and thanks for all the fish.
Hi, Jade! First: Great video. More importantly, second: Thank you for making logic-problem-exploration understandable.
I share your videos with my 10yo son and you #ScienceCommunicator so great that he is able to understand and share opinions on the idea with me.
Please keep doing everything you're doing and be proud. Science communication is a necessity with the way/rate our American education system is failing.
(Putting our son into an online academy next academic year)
Edit: My understanding of the American education system is relatively unique. I graduated high school at 14 by completing a state test, and both my parents were teachers in the California school system from 1969-2004.
I was an '82 baby, so I feel I qualify to give an accurate description on how the American education system changed over the past 40 years.
Parental teachers at my birth + raised by teachers/"professional-student" in college from 1998-2012, then forced to choose a major and got bachelor's in 2016, and have a kiddo 10yo in the education system.
Yeah. We've downgraded over and over and over again.
Cogito ergo sum.
so happy to have an new science based channel to sub to, youre doing great work, keep it up
Thank you for a great video. Somehow you've managed to turn make a very challenging problem easier to understand.
I'm currently working my way through some ideas involving information theory that might have something to say about NP completeness, especially why individual problem instances are often solvable in P time but the general case is not.
In particular, there are 2**(2**k) boolean functions of k inputs, since there are 2**k distinct assignments to input variables and 2 possible outputs that that assignment might have, so you can imagine a guessing game in which Bob picks a boolean function and Alice has to guess which one it is, based on choosing some variable assignments and trying to reverse engineer the rules to gain enough Shannon entropy to identify the function. If the function is chosen uniformly, then you need 2**k bits, log2 of 2**(2**k), which sucks because the relationship between number of guesses and number of bits gained is linear.
But every boolean function can be represented by a countably infinite set of boolean formulae. Each such formula is represented by a binary tree with input variables as leaves and 2-bit boolean gates as nodes, but the number of leaves in the minimum formula is *different* for different functions. What if the probability of each boolean function is determined by the number of leaves in the minimal formula(e)? You could take the logarithm of the number of leaves to transform it into a "function entropy", and use that plus information theory to compute a consistent probability distribution so that low entropy functions are more likely than high-entropy functions. The guessing game then becomes a matter of Alice constructing a series of function models and then using her questions to disprove them.
That doesn't solve the problem of NP-completeness entirely, because I haven't figured out exactly how to relate the boolean function guessing game to the SAT problem yet. But it feels like a promising line of thought, since it's giving structure to the guessing step in NP's definition, and the intractability of P vs NP comes from the fact that we're treating NP instances as unstructured black boxes (which is a requirement for the standard proof technique, oracle relativization). In essence, SAT instances that are almost always true or almost always false are easy to solve because the boolean expressions involved are lower entropy, compared to SAT instances that are true or false with closer to 50/50 probability. Basically, the expression tree in the hard instances is full of XOR and XNOR operations, because those are the 2-bit boolean operations that have 50/50 truth tables, and 50/50 truth tables maximize the information entropy of the outputs over the input space.
Have you published any papers of any type or quality anywhere? This is a genuine question; I’d like to read more of your thinking.
Except that if you have only XOR and XNOR constraints, then you have a formula the encodes a system of linear inequalities modulo 2, which can be solved in polynomial time using Gaussian elimination.
I love your energy, makes these videos so fun to watch. 💜
This is so well made. I watched on nebula, but came here to write a comment.
The finale showing SAT reduction of clique was so clear. I took a graph theory class in college and never understood that concept.
Beautiful and smart and very helpful and friendly, you are such a joy to watch and listen and to learn from, Jade. Simply the best ! Best wishes and hope to see more of your work.
To me, this is related to inductive reasoning or intuition. Example
Captain Kirk is in his captain’s chair surrounded by enemy craft. He’s been in many similar situations before and executed evasive maneuvers that worked and even though this one is not exactly the same as any of those, it’s similar to several that he has grouped together in his memory as a “class” of problems. He knows that there is no 100% guarantee of success, he chooses the class of solution that has the highest degree of success. Some would call it inductive reasoning, others might call it intuition,but since non-acting means death or 0 success, he chooses a high probability.
This is the best video on this topic I have ever seen.
Thanks you so much for this video ! I'm a computer scientist but did not study (or didn't listen ?!) the NP things, the problem is very well introduced !! Thank you so much !!
Such a amazing video...very well explained and putting it simple at the same time...thank you for creating such a valuable and amazing content.
Yes! This is always a fun topic that could use a more in-depth look! Thank you!
This reminds me of a music problem one of my friends had. You had a find a major, minor, diminished, and augmented chord using all 12 notes without repeating notes. Before I solved the problem, I realized there must be 3 solutions ( in one key, there are 12 keys, so 12*3=36 solutions total). That is because an augmented is smmyetrical with 3 equally distant notes. All I had to do was find one solution, and I could figure out the other two solutions. I also did not have to solve the problem to know there were 3 different answers. If one of the elements is symmetrical, then this can save you a lot of time. Perhaps that can help.
And yet another brilliant video! Well done and well worth the wait
A simple explanation to a problem I wanted to deeply understand for years. THANK YOU.
Explaining the hardest class of problems is quite tricky and difficult itself, this is one great video about it. I'd venture to say it's a better overview that the accounts given by some textbooks.
thank you :)
@@upandatom To paraphrase on my compliment: the venerable "Intro to Algorithms" 3rd. Edition book by Cormen et al. explains only in a footnote on p. 1064: 'The name "NP" stands for "nondeterministic polynomial time." The class NP was originally studied in the context of nondeterminism, but this book uses the somewhat simpler yet equivalent notion of verification.'
So basically they have all of chapter 34 (more than 50 pages on its own) to go over NP completeness, yet they actually never directly explain why that N was chosen for that name, what it really entails, except as a side comment in that footnote. And I find quite questionable whether their notion of verification is "somewhat simpler," in fact I take their approach as a bit obfuscating. At least they added in their footnote a reference to Hopcroft and Ullman's "Introduction to Automata Theory, Languages, and Computation," where NP completeness did get presented in terms of Nondeterministic Models of Computation, and where they do have even a highlighted box elaborating the question "Is there anything between polynomials and exponentials?"
All in all, imho your wonderful graph @ 8:02 alone is sorely missing, and would greatly improve quite a few textbooks that cover NP completeness.
"But what if you were actually popular?"
Hello, police? There's been a murder and it was me.
Best video about NP problem I have ever seen. Thanks for the great work!
Jade, I subscribed to your channel after watching just one video, this one is really good the foundations of computer complexity theory
That is the clearest definition of algorithm I've ever seen. Thanx Jade 💗
I enjoyed your Turing video...I also had to use state machine diagrams to clarify functionality to clientele and to programmers.
Your efforts to make us understand these important and exciting things are great. I am very thankful
Great Video 🤩!!! I have been waiting for this since long time .... Amazing !
Glad you liked it!!
@@upandatomyeah and i love you ❣️😍
1st ~ Thank you very much, I enjoyed that.
2nd ~ When I studied this stuff, the way into it was looking at sorting algorithms. We did swap-sort, bubble-sort, merge-sort... and ended up with quick-sort, which on small N, didn't look quick at all. But once you get to N over perhaps 50, Q-Sort becomes radically faster & more efficient than the others.
An excellent exercise for beginner programmers, is to write an implementation of each one, with a graphic representation, so the audience can see what a merge-sort does and how it differs from a bubble-sort.
This group of exercises, leads naturally and logically into discussing complexity and completeness, and if done early in the course, it leaves the student with a clear idea that computers are fast, but that speed can be easily defeated by some kinds of logical problems. They then showed us the Traveling Salesman problem.
We can dream up and implement fairly effective solutions to that, but those are not brute force solutions.
They don't give a 'right answer' but they can pretty easily give one that's better than 95% or 97% of other possibilities.
Another example, is the chess player. The key part, is you need to brute force maybe 5 ~ 6 moves ahead, and then branch. You abandon all play through of games / cases / situations that lead to very poor outcomes. The tricky part is knowing when to abandon a path and chop that branch off the decision tree. But the first trick, the main one, is you don't try and brute force the whole thing.
This leads naturally into the story of Go, and the AI ~
The way AI works, is like a blink reflex. It isn't a decision making process, it's a lightning fast 'instinctive' reaction ~ a reflex. At best, it is reminiscent of the kind of 'thought' we would call subconscious. But it can deal with some things subconsciously, that are a lot more complicated than what a human being can follow, consciously or not. Like the game of "Go".
Didn't get much of this. I'll need to watch it again - several times. Love the animations.
You mentioned in your video about the Principa Mathematica that you were going to make a video about Gödel's incompleteness theorems. I for one would love to see that video!
24:42 So the Sat problem is like listing all the states that your computer’s memory (and registers! could have.
Obviously, since your computer can play every single frame of every movie, or hold every character of every book, or hold a spreadsheet of the traffic patterns of any city. This is an unfathomaby huge number of possible states, but it is finite, and the states that satisfy a particular requirement could, in theory at least, be listed.
There is slight difference between Turing machines and BSM (bounded-storage machine) by the way.
Wow. Great vid. A lot of work went into this...
I remember when I did my electrical engineering BSc and in my first semester I had this course called "basics of computation science". as a guy who loves mathematics I really enjoyed it and my professor was a huge mind (he was a mathematician professor). we were studying about combinatorics, graph theory and discrete mathematics in general. at some point we arrived to this topic (P vs NP etc.) and we started to solve certain problems where the task was to determine if the given problem (that consisted of an input and a question) is an NP (or NP-complete) problem. so basically we had to reduce the given problems to some known NP-complete problems (we usually used the Hamiltonian circle problem for this) in order to prove that they are NP problems. and during these exercises I had an idea: what if the input is a problem's input and question, and the question is whether the provided problem is an NP problem? then the question: is this "meta-problem" an NP problem? after I asked the professor about this self-referential question he was just staring into the void for half a minute or so. then he admitted that he has absolutely no clue but he really liked my question.
What you asked the prof was equivalent to the Russell paradox, which stopped dead Bertrand and Alfred from completing Principia Mathematica. And of course that fed into Gödel, who demonstrated that they bloody well had to stop. ;-}
@@garyknight8966 well, I am not sure what you meant by that. what do you mean by "equivalent to the Russell paradox and Gödel's incompleteness theorems"? I am pretty informed in these topics so I would really appreciate if you could explain it in more detail.
if you referred to the self-referential feature of my question, then yes, it is similar to the Russel paradox and Gödel's incompleteness theorems in this aspect, what is more, even the halting problem and the liar paradox (actually every mathematical paradox) are based on self-reference.
but to be honest I wouldn't claim that these are "equivalent" problems just because they share a certain attribute (namely this self-reference nature), even though I do believe that this forms the core of these problems, because they have very different aspects as well (e.g. Russel's paradox and the liar paradox are contradictions, Gödel's theorems are fundamental limitations of formal axiomatic systems, the halting problem is a fundamental limitations of computability among Turing-machines and so on).
so I think I partially understand what you meant, but please confirm what you mean by the equivalence you mentioned.
ps: this NP-complete thing is also self-referential in a sense, as this video demonstrated. an NP-complete problem is actually a problem that can be both solved by non-deterministic Turing machines and can simulate, i.e. create, non-deterministic Turing machines. and this reflexive relation actually encodes a self-referentiality, which also means and guarantees that the solution of an NP-complete problem is a universal solution for an entire class of problems.
@@_kopcsi_ Ditto kop1k4 .. I agree that NP-completeness entails self-referentiality in a sense akin to Russell's paradox, because it means that the class of problems if solved requires a super-class of which little or nothing can be known in terms only of the solved class. This gives new meaning to the power or meaning of a truth and method that is to be guessed (and guessed just rightly). That feature is reminiscent of Feynman's parametric integration method, which some say he pulled out of the air.
Likewise, demonstration (proof) that a Gödel sentence is true - like perhaps some of the famous unsolved mathematical conjectures, which may well be unprovable within consistent first-order mathematical logic - would require acting in a meta-logic that transcends the constraints of arithmetic (including the excluded middle) and whose own terms and rules could not be expressed in arithmetical (or indeed SAT or 3SAT) phrases. It would be a modal logic to be sure; but there is an unending genus of those yet to be discovered .. or should I say invented ?
That mind is of just the right nature to do this was already demonstrated by Turing under a completely different hat: using a brand of modal logic he proved the soundness of the Anselm ontological statement. Best, Gary Knight
@@garyknight8966 thanks Gary for your reply. to be honest you mentioned many many things in a very compressed way, so it's pretty hard for me to extract from your reply what you meant by that my question is equivalent to the Russel paradox and Gödel's incompleteness theorems. I still cannot see why. I do see that there are some common characteristics like the already mentioned self-referentiality or the layered structure, but to be honest these are very general features. in reality almost everything is hierarchical.
"I agree that NP-completeness entails self-referentiality in a sense akin to Russell's paradox, because it means that the class of problems if solved requires a super-class of which little or nothing can be known in terms only of the solved class." -- well, this is true for almost everything. e.g. development (in the broadest and most general term) is just like that: to exceed a certain stage or solve a problem you have to step to the next level, which is usually unsolvable by the tools of the current level. so yeah, this hierarchised, layered class structure might be seen as a manifestation of self-referentiality, but I find it a bit forced to say that. in general we could say that almost every process that encodes progression (development, evolution etc.) is like this. this is why a finite formal axiomatic system is unable to be consistent and complete at the same time (trade-off), otherwise a finite system could generate infinite truth. similarly, this is why we cannot create a real AI yet, because in order to copy or just to mimic a human mind, first we have to understand it and have a (mathematical) model about it (so we need to have a model about something that is able to make models about things, by the very thing we want to model). and this is why every development process is "generated", i.e. observable, because if progression was trivial then there were no different stages.
"This gives new meaning to the power or meaning of a truth and method that is to be guessed (and guessed just rightly). That feature is reminiscent of Feynman's parametric integration method, which some say he pulled out of the air." -- well, if I understand you correctly here you actually talked about intuition and the heuristic nature of human cognition (and more precisely logical induction). I agree that on an abstract level this is equivalent to the guessing problem if NP problems. but to be honest considering this aspect I don't see connection and relationship with Russel's paradox or Gödel's theorems.
"Likewise, demonstration (proof) that a Gödel sentence is true - like perhaps some of the famous unsolved mathematical conjectures, which may well be unprovable within consistent first-order mathematical logic - would require acting in a meta-logic that transcends the constraints of arithmetic (including the excluded middle) and whose own terms and rules could not be expressed in arithmetical (or indeed SAT or 3SAT) phrases. It would be a modal logic to be sure; but there is an unending genus of those yet to be discovered … or should I say invented ?" -- this is a bit confusing for me. so you say that in order to decide whether a Gödel sentence is true, we have to go to a higher level of logic? well, it actually makes sene that this layered/stacked/hierarchised structure in general encodes progression. as far as I know there are different orders of logic, but modal logic is another kind of extension of logic. so you say that without modal logic we cannot prove if a Gödel sentence is true? and that arithmetics cannot express it? I do see the analogy with Russel's paradox where the concept of set can have this layered/stacked/hierarchised structure that can lead to paradoxes through self-referentiality. but this topic can sometimes be a bit fuzzy for me. as regards the "discovered vs invented" topic: I think mathematics is both discovered and invented, since the things we represent (represented side) are discovered (e.g. fundamental features and symmetry properties of addition, multiplication and other operators), but the things by which we represent (representer side) are invented (e.g. symbols of numbers, operators, relations etc.).
"That mind is of just the right nature to do this was already demonstrated by Turing under a completely different hat: using a brand of modal logic he proved the soundness of the Anselm ontological statement." -- earlier I read/heard about this ontological argument. is it related to the proof of God's existence, right? well, I do not really see how the concept of God is related to this topic (I don't think it is related). Turing was a great mind but he had huge mistakes (especially later, after the war), and even the greatest minds tend to commit mistakes when they start to deal with such fundamental questions like the existence of God.
Most likely it’s not NP, as it looks too much as a non-trivial problem in Rice’s theorem. As a side example, for the prime factorization problem it is not known if it’s NP-complete or not.
Tremendous feat, your hard work and dedication is inspiring!!!
Amazing video. This was very well done and thought out video. This problem makes sense why it’s a problem. 👍🏾👍🏾
This is the best introduction to NP-completeness I've ever seen. Easy to understand for beginners and still exciting for nerds such as myself (40 years of programming experience, including the last 28 professionally).
Outstanding video! Well thought out, well executed, interesting and serious but with just enough dashes of humor.
Thanks a lot! For the first time I understood what NP really is and the Non-deterministic part of it.
You brought joy to my heart when I saw the look on your face when you finally found that needle in the haystack!
yes , we want more in-depth explanation of topics of computer science in an interactive way ! (Thanks for explaining)
I had no idea what I was watching, as I'm not into math, but this made a lot of sense and got me thinking in new ways. I like philosophy and personal development and had quite a blast imagining what it would be like to just intuit any problem I ran into and have it be correct. Just imagining that ONCE in an embodied way blew me away. A quasi-religious experience. Fun!
Thanks for another fantastic video Jade & team
Can't help but appreciate your hardwork in this video 💯🔥
2:58 🤣I love your sense of humour, well done!
I watched a Numberphile video recently which stated (if I remember correctly) that the fewest number of changes to solve a rubik cube was 20.
Awesome video! Not only a very apt explanation of NP and NP-Completeness, but with excellent humor, too! Any chance you can do a hoodie or enamel pin of the quantum physics design for your merch store? I'd go for either in a heartbeat!
Holy moly, 33 minutes long! You are putting in some massive hours, Jade - well done! Loved the video!
Yay! Thank you!
Wow, thanks! As a computer scientist I always have issues explaining NP completeness to people, I’ll just link them your video next time!
DAMN. This is totally not the video I was expecting and I'm blown away... THANKS!
I got the meaning of NP right away. I had "NO PROBLEM" figuring it out.
Thanks for the attractive and fulfilling tutorial. As a side note, the example given for SAT is a 2-SAT, which is solvable in polynomial time.
Hi, I love this video.
I did not think enyone could explain the NP-problem to me in a way I could fully grasp it (I've had some tries before).
During the video I was wondering if there were going to come some bloopers at the end, I would like to have watched them as well.
You have sutch a great variation in visualisation, I mean so many different anemations, that makes this video so plessant to watch. But still I think it would be funny to see how many times it took to "correctly" pull youre chear to the pc-screen wihout laughin or almost faling.
I'm sorry for my bad English (I speek Dutch).
Enjoy the fall, and the comming winter down there. Greetings from Belgium.
Very much enjoyed the video! Also, I have to say that I actually really like the SAT problem, and a very easy solution to it, is to use elimination. You can quickly figure out that Z is the odd one out. I realize that this is a simplified problem, and when things get more complex it becomes harder to see, but the elimination algorithm still hold up in that aspect. And, by eliminating different node variables, you make it less complex as you work through it, hence it scaling better than a brute force check.
Wow, what an ambitious topic for a lighthearted, engaging CZcams video. This video is pretty amazing!
nice, 33 minutes and I don't know when it all passed :)) thank you Jade
Also, there's a good algorithm that says anyone can finish college in 24 days rather than 28 days later, but if you read the sign on the admissions door it read "No Shoving".
Well done Jade! Tysm 🙏🏻
incredible work from an incredible teacher!! i have zero background in computer science but started getting into the rabbit hole after listening to a podcast featuring Stephen Wolfram. got me really interested in the topic and now i'm happy to have run into this video. you've given me a great intuitive starting point!
You are so lovely and so is your way of explaining difficult issues in simplest way possible
I'm playing this video in the background while working on a problem in this category for my job - sorting out material with a four part robot, from a basically random sequence to a sequence we desire. The domain space is almost unimaginably large, but the current solution is so poor that I know I can beat it.
Your presentation is very fun and hillarious! :) Thanks.
Outstanding presentation of some complicated concepts.
Your videos are clear and informative and clever, but it's your entrances and exits that make me LOL.
I finally understand N=NP problem. Thank U!
I weirdly guessed the solution to the XYZ problem (SAT) right the first time, an educated guess though
What I did was noting that X and Y (unlike Z) both occur three times, twice as they are and once negated.
This implies that X and Y are more useful being ones rather than zeros (loosely speaking, 2/3 chance for each of them being ones), and by exploiting said symmetry between them I was pretty sure they're both ones. The last thing was to check whether Z is true or not, Z is the only variable occurring twice, once as is and once negated, so the situation is symmetric between these two solutions, and the symmetry-breaking part of the problem statement is the (-X or -Z) part, since X is probably one, Z is therefore zero
Grand job. This is one of your best videos 👍
Not gonna lie, this got rather heavy, rather quickly. But that's the beauty of CZcams, this sort of lecture would never make it onto broadcast TV.
Keep up the good work. I'll keep being amazed by those far smarter than me.
Well explained
Subbed
Btw, your simple Turing machine analogy will always return a true.
SAT of course in general is NP-hard. But the example you showed is an example of a 2-SAT problem, where every ANDed clause contains only 2 variables. 2-SAT has a faster algorithm than pure brute force.
Oh my god, I almost started sneezing by proxy as you were rummaging through that straw! Now I am itching just thinking about it😵
This was a great explanation. Lengthy but worthwhile. Allowed me to fill a few knowledge gaps on the topic.
Also, the outro song is a banger!
Very interesting video and you helped me learn a lot about the NP incompleteness theorem, i hope you will have a fantastic weekend and that your life will be framed by a lot of love.