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

Get Nebula using my link for 40% off an annual subscription: go.nebula.tv/u...
Watch my exclusive video on the SAT to clique reduction: nebula.tv/vide...
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.a...
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/...
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

[@upandatom]

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 :)

[@aurelienyonrac]

One of the best video on the net. (In my humble opinion)

[@pingnick]

Sign up and watch indeed! I’m so glad I did!! Thanks again Jade!!! 👁🎬🎬🎬🎬🎬🌈☮️💟😍🥰😘🚀🌌🗽♾💯🤯🤩🤩🤩…

[@pingnick]

@@aurelienyonrac 💯♾

[@josephheslin822]

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.

[@lorenzoblum868]

Hello Jade. Clique comes from a french word which has both pejorative and military connotations... We're doomed.

[@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!

[@upandatom]

Aww thank you so much for the kind words :)

[@paulgoogol2652]

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.

[@Pseudify]

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.

[@paulgoogol2652]

​​@@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.

[@AdrianBoyko]

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! 😂

[@YoungGandalf2325]

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

[@joebaumgart1146]

It's the time it takes, not the actual solving of the problem.

[@qzbnyv]

dw Gandalf. I feel you, even if Joe doesn’t. I’m like that too as of now.

[@orsonankers4127]

Just wait for Bilbo

[@jaideepshekhar4621]

​@@joebaumgart1146r/whooosh

[@jorriffhdhtrsegg]

If anyone asks why i dont go to parties, I'll just send them this video

[@at0mly]

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.

[@hunternelson7627]

Truly one of the most amazing videos I've ever seen on KZbin. 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.

[@upandatom]

thank you :)

[@AlexanderOsias]

I was about to say the same thing!

[@TheRaykool1]

+1 thank you so much Jade!

[@victorcoscrato4899]

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

[@dirkbester9050]

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!

[@garad123456]

@@dirkbester9050 if P equals NP and you know it clap your hands

[@lvmbk3755]

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.

[@upandatom]

Thank you so much 😊

[@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.

[@vigilantcosmicpenguin8721]

But it was worth it to find that needle.

[@DreadX10]

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

[@charllandsberg]

"So did we just solve the clique problem? No continues..." LOL! This was the best moment of all of KZbin this week. Thanks for an awesome video

[@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.

[@NoNameAtAll2]

lucky you I'm dealing with PSPACE-complete nightmare

[@chriswebster24]

That’s neat. It reminded me of my kindergarten thesis.

[@ChappalMarungi]

Slightly traumatic 💀💀💀

[@tomasstana5423]

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 💪💪👍👍.

[@krumpy8259]

what books or software do you use to study that topic?

[@tomasstana5423]

​@@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.

[@sayamqazi]

Look up "P vs. NP and the Computational Complexity Zoo" on youtube. it is pretty good.

[@aaAa-vq1bd]

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

[@firstdbzmaker]

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

[@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.

[@magicmulder]

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…

[@justanotherhotguy]

Did you by any chance study at TUM or elsewhere in Germany?

[@justanotherhotguy]

(comment in reply to @magicmulder)

[@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.

[@nyet_maker7948]

Why is this still a thing? (And i mean in most fields)

[@Rijnswaand]

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

[@fackarov9412]

@@Rijnswaand "Understanding something" is necessary to "helping others to understand it" otherwise end up "helping others to understand wrong things"

[@Dunkelelf3]

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

[@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 KZbin. Thanks so much for doing what you do, and I hope it's fulfilling for you!

[@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…

[@joebaumgart1146]

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.

[@Fogmeister]

Did you see the video about MTG being Turing complete? Search for it.

[@Fogmeister]

kzbin.info/www/bejne/ppXQgHeMjrV3gqM

[@Fadexpl]

Mfw you have to solve the halting problem to win a MTG game.

[@KaiseruSoze]

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.

[@1vader]

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.

[@davidf2244]

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.

[@upandatom]

Thank you so much 🥲

[@hopegold883]

Yes, yes, yes! Everything you said. Thanks for taking the time to write it out!

[@davidf2244]

@@hopegold883 😅🤗

[@davidf2244]

@@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!

[@THeMin1000]

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.

[@wk8219]

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.

[@ThomasGodart]

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

[@guidoferri8683]

Isn't it pronounced differently?

[@ThomasGodart]

@@guidoferri8683 It's really the same prononciation and the same word as "click". We "clique" on a computer mouse, for example

[@guidoferri8683]

@@ThomasGodart I guess I confused it with cliché

[@ThomasGodart]

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

[@ChronosTachyon]

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.

[@asdf8asdf8asdf8asdf]

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.

[@drgocht]

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.

[@Ceelvain]

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.

[@markd.9538]

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 😁

[@grantmnelson]

Minor correction- 2SAT is actually solvable in polynomial time. 3SAT is the one that is NP Complete.

[@jazzman616]

Super late to the party here, but SAT reduces to 3SAT. 3SAT is easier to work with for reductions, which is why it's more commonly talked about, but SAT itself is also NP-complete. Did she talk about 2SAT at any point? I only heard her sat SAT.

[@grantmnelson]

@@jazzman616 she used it for her example at one point

[@glennpearson9348]

Fantastic video, Jade. Love your content.

[@niklaskoskinen123]

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.

[@MrDoboz]

lol

[@HungryTradie]

Or that the sorted state is not possible. So long, and thanks for all the fish.

[@aashsyed1277]

Not only is this video good , it is NP-good

[@scaredyfish]

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.

[@sdjhgfkshfswdfhskljh3360]

There is slight difference between Turing machines and BSM (bounded-storage machine) by the way.

[@1234larry1]

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.

[@samarthtandale9121]

Great Video 🤩!!! I have been waiting for this since long time .... Amazing !

[@upandatom]

Glad you liked it!!

[@samarthtandale9121]

​@@upandatomyeah and i love you ❣️😍

[@DenizenoftheAges]

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.

[@albertwebster4795]

yes , we want more in-depth explanation of topics of computer science in an interactive way ! (Thanks for explaining)

[@SamThe42nd]

I love your energy, makes these videos so fun to watch. 💜

[@Jaylooker]

These non-deterministic algorithms sound like brute forcing but, more cleverly by doing it in parallel. Then, picking out one. This is assuming you have enough storage for all the different states.

[@BradRau]

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.

[@Kneedragon1962]

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

[@MaximumDraculaX]

"But what if you were actually popular?" Hello, police? There's been a murder and it was me.

[@ShlokParab]

2:08 "*what if* you were actually popular " EMOTIONAL DAMAGE

[@surajpatel3044]

This is the best video on this topic I have ever seen.

[@boazyeboah1824]

I got the meaning of NP right away. I had "NO PROBLEM" figuring it out.

[@jhonnyrock]

Yes! This is always a fun topic that could use a more in-depth look! Thank you!

[@SaschaKersken]

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

[@raulsaavedra709]

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.

[@upandatom]

thank you :)

[@raulsaavedra709]

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

[@oysteinmb1]

«But what if You were actually popular?» I am watching a math video, that wont be a problem for me

[@ellerylin7491]

Best video about NP problem I have ever seen. Thanks for the great work!

[@GeoffV-k1h]

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.

[@hb20007]

In the intro, the following example is mentioned: _"How do you complete a level of Super Mario Brothers in the shortest possible time?"_ Based on the papers I found regarding this, it seems that the "shortest possible time" part is irrelevant. The idea is to introduce a newly constructed level and use an algorithm to complete the level or show that it's possible to complete. Completing a Super Mario Bros level in the shortest time possible is usually done through optimizing player inputs and taking advantage of glitches like wall clips. So, it does not seem to be relevant to this topic. Tiny detail but a better way to rephrase the question could be: "How do you find the shortest possible path to complete a level of Super Mario Brothers?"

[@bengt-goranpersson5125]

2:06 - "But what if you were actually popular." Ouch, right in my feelings. -_-

[@qzbnyv]

Ahah the casually awkward shuffle backwards at 5:31 👏

[@SeamusDonohueEVEOnline]

Jade needs a wheeled office chair. :P

[@MagnusRender]

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!

[@GlaucoHass]

The 1970's cartoon representation was so good that I had to go back and watch it again, because I didn't listened to a single word you said lol

[@akshay-kumar-007]

Such a co-incidence. I saw your P vs NP video few hours back as a refresher

[@_kopcsi_]

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.

[@garyknight8966]

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. ;-}

[@_kopcsi_]

​@@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.

[@garyknight8966]

@@_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

[@_kopcsi_]

​@@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.

[@mishaerementchouk]

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.

[@hex9219]

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 )

[@marklonergan3898]

Your logic problem had a small shortcut meaning brute force wasn't the only option - by having (X or !Y) and (X or Y), you have instantly made X the only significant variable (must be = 1), and by knowing that, it makes the rest of them solvable in order: (!X or !Z) - Since X = 1, !X = 0, so !Z must be equal to 1, so Z = 0 (Y or Z) - Since z = 0, Y must be = 1

[@EvanBerkowitz]

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.

[@joel.ds.m]

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!

[@Double_T_G]

@30:10. There's the point. Even if we never magically solve the guessing problem, we at least have a tool for measuring the solvability of a problem. Now I get it. Great video btw.

[@manitoublack]

Not gonna lie, this got rather heavy, rather quickly. But that's the beauty of KZbin, 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.

[@jawadthabet]

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

[@CreatrixTiara]

Question about the clique problem: let's assume that the nodes don't change connections while you're running this program. How viable is the following situation: 1. Make a list of all possible clique groups (so in your example, every possible set of 12) 2. When checking connections, make a note of how each pair is/isn't connected, and have that info be populated into the list. For instance, the first time you scan Alice & Bob and you see they are connection, update every set in your list that has Alice and Bob in it with a count for the connection. So if your list has (a) Alice, Bob, Charlie; (b) Alice, Bob, Daniel; (C) Bob, Charlie, Daniel - (a) and (b) would get +1 to their count of connections. 3. After checking each possible pair, your list should have all connections accounted for. Calculate the number of connections for each set and rank the list according to how many connections each set has. Would this also be algorithmically complicated?

[@compuholic82]

The first step is where it already falls apart. Listing all possible clique groups is already an operation with exponential runtime.

[@punditgi]

Jade is back and better than ever! ❤😊🎉🥰💥💯💭

[@eartphoze]

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

[@rulojuka]

A very intuitive example for this parallel processing of non-deterministic computation is the problem of: having many different sized (non-boiled) spaghetti sticks, which one is the biggest? Deterministic computation would go one by one and save the biggest. Non-deterministic you can just get them all at the same time in your hand, put them vertically in a table and put your other hand on the top. The one that sticks is the tallest.

[@MrDoboz]

as long as you can fit all the sticks in your hand

[@govinddwivedi582]

Your efforts to make us understand these important and exciting things are great. I am very thankful

[@NateEngle]

The fact that NP complete problems are mathematically equivalent doesn't make the task of translating one solution to even a single other problem any less of a nightmare. Much as I found the idea of algorithm verification attractive in the 40 years since I learned how to do it I've never been able to justify the time to do it even a single time, and translation between equivalent algorithms is basically similar to the task of verifying and then unraveling that verification in a different context. It might be a finite process but it's still mind-bogglingly large.

[@Johnrich395]

A joke: A horse walks into a bar. The bartender asks, “why the long face?” and chuckles. The horse saids, “I don’t think…” and he immediately disappears! This is of course citing Decart’s axiom of “I think, therefore I am.” I could have said that at the beginning, but that would have been putting Decart before da horse.

[@ryanraja5170]

You are so lovely and so is your way of explaining difficult issues in simplest way possible

[@Ikbeneengeit]

I'm glad someone finally acknowledged that my Super Mario hobby holds the key to unimaginable technological advancement.

[@sunroad7228]

The Arrow of Energy - "One-Way Entanglement Between Isolated Energies"; "Time taken in stocking energy to build an energy system, adding to it the time taken in building the system will always be longer than the entire useful lifetime of the system. In any system of energy, Control is what consumes energy the most. No energy store holds enough energy to extract an amount of energy equal to the total energy it stores. No system of energy can deliver sum useful energy in excess of the total energy put into constructing it. This universal truth applies to all systems. Energy, like time, flows from past to future".

[@ygorgallina2691]

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 !!

[@TW-lt1vr]

I solved the Rubix cube problem: you take the stickers off and put them back where they belong. They didn't like my answer but I'm probably going to sue since I essentially gave them a free answer :(

[@pesilaratnayake162]

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.

[@johnscott2076]

Wow, Simon must have cracked some kind of code in order to win the Jade prize

[@asdf8asdf8asdf8asdf]

Talk about “satisfiability”! 😎

[@why-no-investigation-reports]

It's "shame" , "regret", "waste" and uncomprehensible adultery.

[@steffahn]

27:27 looks like you forgot the small but important step of also including a condition for (successful) termination in your SAT formula. In order to ensure that a satisfying assignment to the SAT formula does *indeed* represent a run of the Turing machine ending in a YES state, this very fact must be asserted by a constraint such as an or-expression over all points in time that one of the S^YES state variables must be true. I. e. S_t=1^YES OR S_t=2^YES for this simple Turing machine. Forgetting to do so forgets to assign any semantic meaning to "YES" that would distinguish it from "NO". On a similar note, you also forgot to assign semantic mening to "START" in the form of a constraint to ensure that we *start* in the starting state, i. e. the simple boolean expression S_t=1^START.

[@1vader]

You don't actually need to add something for the start in this case since the first part is "((S_t1^START and ..) or (S_t1^START and ..))" which already forces S_t1^START to be true. But yeah, the other part is true, it's easy to check that the formula would also be satisfiable if the last clause were X_t=1^0 which we don't want. It's also not super clear to me how this would generalize to a machine that can take an arbitrary amount of steps though, since we need variables for each timestep.

[@steffahn]

@@1vader Right, good catch. If I recall correctly, you would also want to add more alternatives that allow you to stay in the terminal state indefinitely, and of course in general there are also more states and state transitions, so asserting the START state will become necessary. On second thought, I suppose if we going to be staying in the terminal state, that also means that the final state being YES only needs to checked for the very last point in time, not actually as an or-expression over all points in time. As to the question of generalization, the idea is indeed that the formula becomes really very much quite huge indeed, as there will be variables for every combination of time step and state, as well as for every combination of time step and tape position and tape value. And you would need a copy of the whole Turing machine rule set for every combination of point in time and tape position. The thing that makes all this feasible is then that we only want to simulate the execution of a given *polynomial time* (nondeterministic) algorithm, so the algorithm comes with a concrete polynomial time bound, and you can cut off the set of interesting/relevant points in time, as well as the number of tape cells that could ever be reached, according to the known time bound that the algorithm is supposed to terminate in. Then, even introducing new variables and copies of the rule set for all points in time and all tape positions, as listed above, will still only create a polynomial size formula overall.

[@aaryananand7288]

Tbf, Non-deterministic Computation is becoming more and more possible with all the new quantum computer tech that's popping up now...

[@Flovus]

4:39 It is important to stress that the clique size also increases here. If the clique size is fixed, say k, then the runtime is polynomial (in the graph size) despite the algorithm being brute-force search. 6:20 The sum, product and composition of polynomials are polynomials. This is important since algorithms are often built together like building blocks. The easiest case is when I run an algorithm and then another algorithm: the overall runtime is the sum of the two runtimes. I personally find nondeterministic Turing machines outdated. The definition by deterministic verifiers is more practical and easier to understand.

[@zxuiji]

5:30, (haven't finished watching) For the clique problem I think I would go through each node 1 by 1 and count the number of single link rules matched, then if it matched all the single link rules I would then do the same for the local nodes if they haven't already been visited and then count how many of them carry the same count and mark the original node with that count of local nodes matching. I would then add up all the counts for the local nodes and add them up and mark the original node with a total count, if the count is >= what wanted then no further is needed, otherwise I continue to the next node and do likewise, something like this: foo( node, *count, rulec, want ) { if ( node.matched >= rulec ) { *count = node.linked_also_matched; return node.i; } if ( node.matched >= 0 ) { *count = 0; return -1; } // ... count matching rules if ( matched < rulec ) { *count = return -1; } for ( i = 0; i < nodes.count; ++i ) { n = foo( nodes.linked[i], count ); if ( n < 0 ) continue; total += *count; if ( total >= want ) break; } node.linked_also_matched = total; *count = total; return node.i; } While it would still be an exponential problem it should still be faster than always checking the local nodes against the rules

[@darkphoenix68]

Y'know, it occurs to me that Matjaz Leonardis (at around 18:50) says our language ("English") has the ability to describe everything, and then he gives some examples, including "everything". But if there is something that English cannot describe ... would we even know it? Or would it be outside of the "everything"? I'm sure there are at least a few concepts that exist in other human languages which have no direct equivalent in English -- and some of them can be difficult to accurately describe. There are also concepts in science and mathematics that do not easily map into "natural" spoken and written language. But hey, maybe that's a question for the linguists, or the philosophers...? 🙂

[@mysteriesinmind]

Your videos are clear and informative and clever, but it's your entrances and exits that make me LOL.

[@polypro553]

So here is my idea to solve the Clique Problem (Or at the least to possibly reduce the computational power to solve) I am still trying to create a full procedure, but let's get some of the basics out of the way. Let's refer to my scenario as asking if there is a clique of 4 or (x) the number of nodes (y) and number of connections each node has (z). First Algorithm: Easy (not all problems will be solved with this algorithm, but it's the fastest, plus any progress can be transferred to another algorithm) We can remove a node if Z is less than X-1. Any left will be referred to as possible nodes. We can determine if a clique DOES NOT exist, if possible nodes < clique of (x) We can determine a clique DOES EXIST, if all remaining nodes have x-1 connections After this go to the next algorithm. Second Algorithm: More advanced Search for an unlikely node - we can label a node as unlikely nodes if it is = X-1 If the algorithm detects an unlikely node, immediately test it. If a clique forms, then the problem is solved. If a clique does not form, you can remove that node and any corresponding connections. Update the number of nodes and connections and see if the clique is still possible. (Go to first algorithm) In theory we could modify the second algorithm for more different amounts of connections ( ie 4, 5, 6, ect) but will require more brute force. If no nodes, exist go to the next algorithm. Algorithm 2.5 : Very computational Test if there are connections between the nodes with the lowest amounts of connections. (ie if there are 2 nodes with 4 connections each) If there are connections, then test if there are any possible cliques that forms with both nodes. If there is, then the problem is solved. If a clique does not form, then remove that connection and update the remaining nodes and corresponding connections. (Go back to the first algorithm) I don't know if algorithm 2.5 is computationally more efficient or not. However, the less connections in general, the quicker it would be to computer. Please reply if you have any ideas, I want that million dollars.

[@Ailun__]

You’ve easily explained this way better than most professional computer scientists could have. Amazing job, wish I’d seen this while I was still in college.

[@stevepoper8073]

I got really interested in P vs NP when watching your other video. So excited with this video!

[@apophissoftware]

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.

[@blahdelablah]

On the boolean logic problem around 17:50, there is a way to determine the answer with logic rather than brute force. If (X or !Y) and (X OR Y) have to both give a 1, then X has to be 1, as otherwise !Y and Y would both have to be 1 which is impossible. After you know X is 1 the rest falls into place. (!X OR !Z) means that !Z has to be 1, which means Z is 0, and if (Y OR Z) has to be 1 then Y also has to be 1.

[@contessa.adella]

The other issue with your clique nodes algorithm is you’ll get the ‘Deep Thought computer’ type answer instead of the specific data points you really want to know about. You: Can I make a party of twenty from these fifty people? Algorithm: says “yes”. You: Great! So who then? Algorithm: ?…That was not the question.

[@unconnectedatgmail]

Thanks for Nebula!

[@karldavis7392]

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.

[@reynoldskynaston9529]

I don’t know how it took me this long but I finally realized that the simple Turing machine is just the same thing as the cpu, the stack, and the stack pointer. Pointer points at the current instruction being dealt with on the stack. The cpu reads that instruction and does what it’s told (including writing the pointer to somewhere else). Then the stack pointer increments pointing the cpu the next instruction.

[@user-wg2vo1vx8h]

I could never find such a great vidoe on this topic !! A huge thanks. Keep up the fascinating work. Cheers to Up and Atom :)

[@bugsbane]

needle in a haystack is easy right? as long as the needle is either 'magnetic' -(in which case use a strong magent) or significantly more dense than hay (in which case use a pool of water). it's harder to find a specific needle in a needle stack. Oh - and I guess you can also burn the hay and sift through the ashes.

[@CoreyMinter]

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.

[@bazsnell3178]

You brought joy to my heart when I saw the look on your face when you finally found that needle in the haystack!

[@polychoron]

That is the clearest definition of algorithm I've ever seen. Thanx Jade 💗

[@purpletiger9313]

Jade mentions "satisifiability problems" or SAT. I studied this when I was doing optimization for energy-efficient building design, and actually had a SAT solver (as they're called) written in C++ that was open source from a graduate student at an Australian university. The code would take a file with all of the boolean constraints and spit out the answer if there was one. And the boolean constraints, even in coded form, could sometimes be pages. It was pretty cool, but unfortunately I lost the code when my hard drive crashed (a while ago on a computer far far away), and the code is no longer posted online. Easy come, easy go!

[@Michael-kp4bd]

I’d assume it has to perform exhaustive search, as it is NP-complete.

[@ThisFinalHandle]

I remember a documentary called Mean Girls where I think they solved the clique problem. It had something to do with a school bus.

[@williamlangley1610]

I have not been able to convince software coworkers that we must stick to algorithms which are always one of three: "contiguous", "if-then", and "general do". What makes this rule effective is that every one of these constructs has one input and one output; thus confusion and errors minimized. (Just thought you'd like to see this.) Some do not realize the concepts of "object oriented" can also make algorithms significantly more "relatable". Thanks for your services to help conceptualize.

[@fypacademy]

For naive mind on computer science like me , it took me watching "P vs. NP - The Biggest Unsolved Problem in Computer Science" to slightly understand this one,Thanks for mentioning it.