The Math Problem With a $1 Million Prize for Solving

Go to MadeInCookware.com/HALF, and use promo code HALF for 15% off your first order
Get a Half as Interesting t-shirt: standard.tv/collections/half-...
Suggest a video and get a free t-shirt if we use it: halfasinteresting.com/suggest
Follow Sam from Half as Interesting on Instagram: / sam.from.wendover
Follow Half as Interesting on Twitter: / halfinteresting
Discuss this video on Reddit: / halfasinteresting
Video written by Ben Doyle
Check out my other channel: / wendoverproductions

[@16jms]

Fun Fact: The man who solved the Poincaré Conjecture, Grigori Jakowlewitsch Perelman, rejected the prize money and told the congratulatory committee to get lost because he just wanted to be left alone.

[@sabersz]

I saw the video Count Dankula did on that "It's a million dollars man! Just take the money!!" 😂

[@hoze1235]

count dankula made a video on him

[@MrPillowStudios]

@@sabersz Some things in life are so unbelievable. That you deny them.

[@lool12366]

He returned the money because they didn't recognize another professor that did a lot of work in solving them.

[@imveryangryitsnotbutter]

@@lool12366 Why didn't he just give the money to that other professor, then?

[@RodrigoBadin]

The thing is: If you had the formula you would earn way more money by solving the problems selling your services to solve rather than selling the formula for a million USD.

[@fetchstixRHD]

You would have to play pretty stupid though, otherwise you would very likely give away how you proved it (or enough to deduce how to do so) and so you’d lose the advantage you have. If you’re smart enough to know how to solve one of those problems, you would very likely get a lot more money from others as a result, either through jobs or otherwise.

[@TheStrongestBaka]

But it's likely that the "formula" doesn't exist and a million dollars would be awarded to someone who proves that.

[@user-cj2zt3zu1t]

@@TheStrongestBaka There's also the case where the formula exists, but just proving its existence (without finding the formula itself) will also give 1 million.

[@Mexican00b]

@@TheStrongestBaka you cant prove a negative tho

[@mrchezsandvich.4096]

@@TheStrongestBaka cirno

[@imperialpilot2164]

Just give me 3 flintstone gummies, I'll handle them.

[@Potatoinator]

You'll overdose.

[@DreamPhreak]

You're a madman! You'll break yourself with that many flintstone gummies

[@CryptikSpectre]

@@Potatoinator but before they do they'll solve it nah I'm kidding they will just die

[@ARandomCanadian]

Nobody has ever survived that many before... are you sure you’re ready for this? To sacrifice your everyday life to fall into a flintstone gummy spiral? Sacrificing your life for a math problem, don’t get me wrong it’s brave, but your life will never be the same. Are you prepared for this?

[@weebishusername9288]

Take 3 and eat all your vegetables

[@Kari.F.]

Yay, I'm about to become one million $ richer. I remember something about Paul having 10 apples and giving three of them to Mike, so I'll just take it from there and start working on this. Easy peasy!

[@NuclearTopSpot]

That's not a math textbook problem. Paul needs at least 4 carts of 20 pineapples. Now Mike wants to trade 6 peaches for 1/4 pineapple each and 9 of his pubic hairs for 1 pineapple each. How many Pineapples has Paul eaten in the meantime?

[@alexiscandia7492]

@@NuclearTopSpot 2 1/2 pineapples. Unless you count the one in his ass. Then 3 1/2.

[@mikebar42]

I'll beat u to it

[@notyourfriendlyneighbor2733]

Tell us how it goes

[@mikebar42]

@@notyourfriendlyneighbor2733 turns out p doesn't equal np 😤😅😭🤔🤣

[@pvic6959]

me a computer science graduate: ah yes, my nightmares have returned

[@2011blueman]

Yes, comp theory was my least favorite course in computer science. My running joke in the course was to ask if the person the theorem or proof was named after had gone insane (they pretty much all had). For example, Alan Turing, Kurt Gödel, etc.

[@lerquian1970]

It was a nightmare but at the same time pretty interesting, in particular the p=np problem. I don't know why there aren't more videos about this.

[@Sparrowly1]

Lmao I was thinking the same

[@pvic6959]

@@2011blueman I actually really enjoyed it but holy crap, those algorithm classes were some of the most difficult I took. I was always amazed by the solutions these people came up with and then I remember they did it decades ago... and now its taught in undergrad CS classes LOL. I was very fascinated by it all, but I could probably never come up with that stuff. the comp sci people of long ago were straight up geniuses and im here like...

[@pvic6959]

@@Mathguy363 lol my analysis of algorithms course was basically straight up math. we didnt write a single line of code for that... unless you wanted to for fun, which I did because im a nerd lol

[@yonatanbeer3475]

To be clear, even if we have a polynomial time algorithm which solves NP problems, it could still in practice be unhelpful, e.g. it could have constants greater than a googleplex or whatever and only be efficient for inconveniently large inputs.

[@MABfan11]

" e.g. it could have constants greater than a googleplex or whatever and only be efficient for inconveniently large inputs." *Googologists have entered the chat*

[@neeneko]

heh. years ago I remember working on a problem like that. we had two possible algorithms. I was working on one that starts off really well but got exponentially worse as the dataset got larger. there was another that had a high setup cost (and expletive ton of RAM), but once you got everything cooked (constant+linear) put into memory (linear), the solution also became linear.

[@f52_yeevy]

I’m sorry that it’s unrelated, but I couldn’t help but notice the lick

[@stardestroyer19]

Also would the P=NP proof necessarily be constructive? If one could show that its possible to solve things in P time would it necessarily make it easier to find the algorithms? I understand that knowing that it's possible would be helpful but it wouldn't immediately resolve that issue.

[@vojtechstrnad1]

Or it could have a complexity of O(n^100), which is polynomial but not practical.

[@stardestroyer19]

> One of them has gotten significantly more attention and more failed attempts than the rest. *The Riemann Hypothesis would like to know your location*

[@frederickm9823]

Thats what I thought too. Then I realized that the RH is probably not very suitable for HAI, since it might be difficult to explain in a simple way 😄

[@stardestroyer19]

@@frederickm9823 Oh it is, you'd have to talk about convergence, complex numbers, applications to number theory and a whole bunch of stuff that's difficult for someone without a maths or physical sciences background.

[@frederickm9823]

@@stardestroyer19 Yeah. You can't really describe the "core problem" without explaining a lot of background stuff. As somebody who wrote his bachelor thesis about elliptic curves, I am very interested in the Birch Swinnerton-Dyer hypothesis, but man, if I had to explain it with simple words, I would fail miserably 😄

[@PrestonFlanders]

I have been waiting for this comment

[@stardestroyer19]

@@frederickm9823 I know how it be man! I'm a PhD student in theoretical physics and somethings could take a long time to explain if you want to make sure people get the core idea of something without watering it down so much it becomes too simplified.

[@Yamezzzz]

A $3 million muffin is the exact opposite of a "very convoluted money laundering scheme". In fact it might be the least convoluted money laundering scheme of all time.

[@vojtechstrnad1]

Someone needs to try this and see if such a simple scheme can actually work.

[@eldritchperfection213]

oh so what if I create a company which concept is to give money to people which i obtain from other companies and the people that watch me launder money. why does i have the impression someone already did that before

[@kantpredict]

Like a $1tn coin to avoid the debt ceiling simple.

[@mastershooter64]

@@vojtechstrnad1 it's called buying and selling art, they already do it. You ever hear of shitty paintings getting sold for millions of dollars? yeah...

[@HipyoTech]

Thanks for the callout... 0:08

[@jeremoo]

hey but now you have keyboards 😦👍

[@Husqy]

lol nice

[@Lhamb]

hipyo tf you doin here

[@harrypotter5460]

Fun fact: The man who solved the first Millennium Prize Problem turned down the $1,000,000 as well as the award, and later a Fields Medal. He then quit his job and went into seclusion. When approached by a writer in 2012, he stated “You are disturbing me. I am picking mushrooms.”

[@harrypotter5460]

Source: en.wikipedia.org/wiki/Grigori_Perelman

[@pauraque]

Fedex: thx for solving the hardest problem in the world Me: np

[@imveryangryitsnotbutter]

Gödelmmit

[@nguyenduyphuc3924]

*slow claps*

[@jimsvideos7201]

This fkin guy right here.

[@eclecticsoffy]

@@imveryangryitsnotbutter Your reply is incomplete

[@hashxz]

Why do I feel like half as interesting son will make a video in 2069 titled "why did they 2020 Olympics happen in 2021"

[@CinemaDemocratica]

...Because Covid hadn't already killed enough people by the time 2021 came around. #FIFY

[@dompedroii4656]

Kkkkkkkk true

@@dompedroii4656 Better not use the "brazilian laugh" in other languagues.

[@hipato6838]

@ KKKKKKKKKKK

@@hipato6838 Not again.

[@PrestonFlanders]

“One of them has gotten significantly more attention and failed attempts to solve it than the rest - P vs NP” *Riemann: Hold my hypothesis*

[@frankkobold]

Well, I would say every math student was at one point trying to proof both, but at least p=np was also tried by some computer scientists^^

[@Vaaaaadim]

@@frankkobold "but at least p=np was also tried by some computer scientists" guilty as charged

[@jolly6537]

@@frankkobold I (a CS student) can confirm I've tried to proof that P=NP and P!=NP and failed at both. I don't even know what the Riemann hypothesis is though :D

[@thesnippa_x_killa5725]

I have a feeling that Sam wants us to solve this, so he can claim the money.

[@tomx641]

$1m isn't that much. It's a lot of playstations, but it's not a lot of years of salaries for well qualified people, buildings etc.

[@ethanl.1699]

@@tomx641 if it’s not taxed, it will still give someone who makes 100k a year 10 years of salary considering their salaries are also not taxed

[@tomx641]

@@ethanl.1699 It all depends on contractual terms, but I'm talking about Universities in general.

[@ethanl.1699]

@@tomx641 for a university professor, it’s still a few years of work saved, but yes, it’s nothing compared to a building lol

[@tomx641]

@@ethanl.1699 University professors get grants for millions all the time and it lasts them hardly any time at all. No idea where the money actually goes, just that it doesn't seem to last long.

[@so-ares]

It would make more sense if the promo code "half" gave 50% off...

[@mikastrae]

missed opportunity to say 15% as interesting, tbh

[@Lilgugger3712]

Its supposed to make money not sense dear

[@60secondfinance81]

Next video on Wendover Productions: The Logistics of Why You Should’ve Paid Attention in Math Class

[@thetimebinder]

So, basically this video on how to survive The Cube kzbin.info/www/bejne/jpy8p6JsiJ1lgqc

[@marsgal42]

I too assumed this would be about the Riemann Hypothesis. As a long-time computer nerd techie type I've followed P=NP for a long time.

[@zunaidparker]

After the intro I thought for SURE we'd be talking about the Riemann Hypothesis. Not sure if P=NP is more studied than RH.

[@vojtechstrnad1]

Well arguably P vs NP is the most accessible of the problems, unlike RH which uses complex analysis and the other five which I barely know anything about. But yeah, if he ever makes a video on another one of the problems, it will be the Riemann hypothesis.

[@zunaidparker]

@@vojtechstrnad1 When he does I'll click on it so fast!

[@poisonpotato1]

Me too. The only ones I somewhat heard of was P vs NP, Navier Stokes and the RH

[@user-semenar]

The proofs that P=NP (or P=/=NP) are appearing several times per month nowadays. It might be not studied more, but it certainly attracts a lot of attention.

[@sebastiane7556]

Short addition: a problem in P does not have to be "easy" or solvable in a fast way. Let's say I would find an algorithm for the TSP problem with a constant runtime of hundred years. That would be O(1) and in P, but probably wouldn't help me to hack any bank account.

[@JanStrojil]

That is a very good point. I also find it strange that most videos on P=NP seem to equate proof that P=NP with breaking encryption. Proving that a solution exists does not necessarily lead you to that solution, or does it? So knowing that a polynomial solution exists may put the encryption on shaky grounds but it will not magically make it not work overnight. Someone still has to find that solution.

[@QuantumHistorian]

Also, one could have a proof that P = NP that is not constructive. So, contrary to what is said at 1:50, just proving equivalence does not necessarily lead to new algorithms. And, even if it did, it's entirely possible that an algorithm in P has such a huge overhead that it's slower than a corresponding algorithm in NP for any input we might be interested in. This entire video is riddled with mistakes.

[@YannickJadoul]

Yes, but the thing is: an actual algorithm would to some degree only be a side note. Breaking this exponential barrier is much more significant in itself. Any polynomial algorithm (even the one with a enormous exponent or huge constant inside the big-O) would still exploit some kind of non-trivial structure and would most likely mean there would be some insight into this class of problems. So very likely, even if that's the case, it's the crack in the problem that opens up a whole range of new research that will in all likelihood bring down the polynomial's constants and exponents. But I also don't think you can find lots of experts that believe this would be the case. As far as I know, it is believed that it's much more likely that P != NP.

[@vojtechstrnad1]

It might be a bit confusing to suggest there could exist a constant time algorithm for the TSP. Trivially it's at least O(n).

[@Vaaaaadim]

@@JanStrojil "Proving that a solution exists does not necessarily lead you to that solution, or does it?" It doesn't, your understanding is certainly correct. "So knowing that a polynomial solution exists may put the encryption on shaky grounds but it will not magically make it not work overnight" Very well phrased. More to the point, simply knowing the answer(yes or no) to P=NP is not much better than pretending you know the answer, it would only tell you whether or not your attempts at a proof for or against are futile or not.

[@boium.]

0:56 Oh boy, I'm a math student and I seriously tought that when you said one has gotten more attention than the rest, that you were going to talk about the Riemann Hypothesis. Would have loved an episode about that but P vs. NP is also a good one.

[@tetsi0815]

The core of P=?=NP is way easier to explain in like 5 minutes than Riemann. :-)

[@bulgaria9003]

We did it. The "Who Wants to Be A Millionaire?" in math is here.

[@GURken]

Perelman clearly didn't want to.

[@stardestroyer19]

@@GURken Perelman is a russian wizard. He has no need for earthly goods.

[@janno288]

This isn't going to fix your dept greece. (I'm greek myself so dont start ww3 here)

[@weebishusername9288]

@@GURken "I'm gardening"

[@bulgaria9003]

@@janno288 wow I'm not the only Greek youtuber...

[@SanderDoesThings]

The math problem my mom expects me to solve after watching the 3 minute video

[@calvinbouroughproductions8321]

The "Hey, you want to get rich quick" with the guy standing there with his finger at the beginning sounded like an advertisement for Honey.

[@AbiGail-ok7fc]

You get the reward for settling the P =?= NP problem; winning it doesn't have to mean that P = NP. Furthermore, even if you prove that P = NP doesn't imply you have a non-exponential algorithm for NP problem. (Having such an algorithm of course means P = NP, but the reverse doesn't). (Also, an algorithm which takes n^1000000 steps technically is in P, but in practice, that won't give us efficient algorithms)

[@Caesim9]

How again does P=NP not imply a polynomial algorithm for all NP problems? I mean of course there may be non-constructive proofs but in theory there should be algorithms.

[@NerdTheBox]

@@Caesim9 I think Abi's saying that it's possible to prove that P = NP without actually coming up with a formula for an NP problem

[@Vaaaaadim]

@@NerdTheBox indeed, a --"nonconstructive proof" would be accepted-- just noticed the first reply literally said non-constructive proof oopsie

[@Vaaaaadim]

Actually, I see we're all latched onto that idea of non-constructive proofs being a thing. I think @Caesim9 is saying, regarding the statement: "Having such an algorithm of course means P = NP, but the reverse doesn't" he interpreted it to imply "even if P=NP that doesn't mean a non-exponential algorithm exists", which would be wrong, its definitely the case that if P=NP then such an algorithm does indeed exist.

[@Think_Inc]

Imma pretend I understand that.

[@tyelerhiggins300]

The whole calculator part is exactly what I have to go through when I tell my students about these problems. One of my students was convinced that they found a counterexample to Goldbach's conjecture (not one of these, but still an open problen) when I couldn't immediately tell them 2 primes that sum to 1,000,000.

[@lerquian1970]

The interesting thing is that the opposite hasn't been proved (although is the same question tho). We can't prove they're the same, but we can't prove they're different things either.

[@Danielle_1234]

Yep. I'm pretty sure P != NP but don't know how to prove it. Maybe going over the axioms of the system questioning its provability incompleteness theorem style or something in that ballpark.

[@PCGeines]

I thought a way to solve the P-NP conjecture. Unfortunately, this comment bar is to small for writing it in.

[@Xontaro]

Fermat, is this you?

[@TechKidShazil]

Classic Fermat😂

[@Sauce042]

Whose Fermat?

[@mmay3315]

2:51 this graph also applies to other activities

[@michadmochowski1246]

Literal utopia, we all know it's too good to be possible, but good luck proving that as an abstract

[@minecrafter0505]

At 1:26 I took my TI-84 plus into my hand and silently whispered "He didn't mean it!"

[@slamwall9057]

Does P = NP? Only if P is equal to zero or if N is equal to one

[@xplayerfireone]

Or P is 1 and N is also 1

[@AltayHunter]

3:20 Unfortunately the problem described here is not equivalent to the traveling salesman problem, and actually could be solved with a greedy algorithm within polynomial time. The mistake in the video is that the points are labeled in a particular order and the difficulty is being described as finding the streets to take to traverse them in that order. This is equivalent to graph traversal and can be solved in linear time using the A* search algorithm. The key point that makes traveling salesman an NP-hard problem is that you're not given a particular order to traverse the nodes. Checking every possible permutation of the nodes is what makes it explode into factorial time.

[@Nancy3]

Why can't math grow up so it could solve it's own problems?

[@jamcdonald120]

0:25 I think you forgot the part about having no skills attatched to your degree

[@mohammedbelgoumri]

2:18 It's Actually all the problems that can be solved in polynomial time, not those whose solution time is not exponential. If the time complexity of a problem were say 2^sqrt(n), then it would satisfy your definition because it grows slower than all exponentials. But it would still not be in P since it grows faster than all polynomials.

[@joshuazelinsky5213]

I really like that right after you note about people catching all the mistakes you are about to make, you say that P is things which can be solved in time which is not exponential. But this isn't the same as being polynomial. There are things which have time complexity which is worse than polynomial but still not exponential. For example, the best known algorithm for solving graph isomorphism has this level of intermediate complexity time. But well done video anyways! (Also we do have algorithms for traveling salesperson problem that are better than brute force checking everything. But the savings for it aren't that great.)

[@jonathanmatthews8928]

Your promo code “HALF” doesn’t work. The checkout process says “The provided code is invalid.”

[@TheTransitmtl]

Incidentally it's because the encryption was longer to solve that to verify

[@LudwiQ6]

maybe it applied automatically and now you try to apply the second time, MAYBE

[@daniel.harvey]

Does not work for me either and no there is no discount already applied

[@mastercraft117]

Try using the code WHOLE

[@CinemaDemocratica]

I don't fail to appreciate the smug humour that this has generated, but it's also a quiet scandal and merits some sort of response. Presumably Sam can be bothered to give a shit when his promo codes don't work, but ... it would sure be nice to know for sure.

[@bane2201]

Finally a topic I knew about before an HAI video! Also, in case anyone is wondering why the problems are so difficult to discuss - I'm a senior in a Math/CS double major, and I can only fully understand what 2 of the 7 problems are even asking. I'd bet a lot that the majority of math *professors* can't understand more than 4 of the statements.

[@KarlFrederick19]

Therapist: "Stock Footage Anonymous Hacker Guy can't hurt you" Stock Footage Anonymous Hacker Guy: 4:04

[@Shawn_Carley]

My brother was working on this problem back in high school (~2005). He had his work copy written so as to date it. I have no idea how close he came to solving, because none of us knew what tf he was talking about lol. Will have to bring it up with him the next time we’re together

[@henryginn7490]

Spoiler alert: not close at all. Still, it’s nice to have a crack at problems even if they are famously unsolved by the greatest minds in the field of maths, it can still be an interesting experience and you’ll learn something probably

[@_.Infinity._]

@@henryginn7490 We don't really know, I mean the great minds were not able to solve Poincare conjecture as well, but now it is solved. But yeah, the chances that he wasn't able to solve it are higher.

[@YannisHalliwell]

i watch these when im high and it always fades into commercial in a very sneaky way.. i kinda love it

[@nanoder7te]

As a computer science student i have to complimet you! Awsome 6 minute summary of a topic, i would regard as one of my hardest during my bachlelor degree!

[@harrypotter5460]

Genuinely thought you were gonna talk about the Riemann Hypothesis since that problem is even more studied than P vs NP.

[@sunvieightmaster88]

This is amazing.

[@kkmac7247]

This is amazing.

[@albineriksson2667]

@@kkmac7247 you are amazing

[@albineriksson2667]

Will you marry me ?

[@albineriksson2667]

Please

[@cszulewski]

Smells like desperation in here

[@JPTQJR]

Expected a Navier-Stokes rundown and got an N = NP instead Still loved it nonetheless

[@yonatanbeer3475]

I expected Reimann Zeta, that's the millennium problem that seems to get the most attention

[@bane2201]

Man, I'd be shocked if HAI could figure out the question. Not because I think he's stupid - I'm a senior in a Math/CS double major, and I can't figure out the question.

[@minuspi8372]

2:06 Called me out lol

[@hi__im_zack4890]

You got me, I'm just here to point out all the mistekas 2:10. Well, more of a clarification. The P?=NP problem refers to a specific type of problem, decision problems. That is any problem that can be answered with a yes or no. So, using the traveling salesperson problem as an example the decision problem would be: does there exist a path less than or equal to some given value? For sudoku, the decision problem would be: is a given sudoku layout solvable? Solving these doesn't necessarily mean we would get the solution, just the yes or no answer. As mentioned in the video these are both in NP as they are pretty easy to verify by giving the solution. A lot of problems can be expressed as a decision problem, but a lot can not be. The problems that can't be, like for example playing/winning a chess game would not become easily solvable if P was equal to NP. Well actually the problems we care about are: For a map with n stops, does there exist a TSP path less than or equal to some given value? and: given an nxn sudoku problem, is it solvable? This is because, as you mentioned at the begging, we care about how much the time increase relative to the problem size. Other than that, this was a pretty decent description of the P?=NP problem for only taking like 5 mins. It's funny, this problem is the easiest of the 7 problems to understand what the problem is saying, but that doesn't mean it isn't complicated. I mean, after all, it hasn't been solved while being one of the most attempted problems. The main difference between this problem and other complicated math problems is that for theoretical computer science, which is what field the problem is in, we just abstract out all of the complicated symbals.

[@HPSshorts]

Hardest problems to solve When will be another bricks video

[@pockpock6382]

"Half" should be a 50% off promo code, change my mind.

[@harrisonclark3799]

2:52 they definitely knew what they were doing with the labels on that graph

[@panagiotischristo]

I like the knife segment...thanks. As well great video

[@bhzucker]

Sam: Are you in crushing student debt due to a predatory poverty cycle brought on by late-stage capitalism? Also Sam: Use this code to get 15% off expensive cookware Me, a millennial: He gets us 🥰 take my money

[@CypressJuice]

Am I the only one who actually doesn't want to join my friends at the "P" party....? That's just nasty....

[@Mutxarra]

Wasn't expecting to see Barcelona appear on minute 3:10. Especially just the place where I used to live. Thanks for the surprise, HaI!

[@Alexc99xd]

One of the best moments in my cs class was when our lecturer showed how you can change one NP problem into another (reduction). it's basically saying you show that problem X is at least as hard as problem Y (which you know is NP) so X is at least NP. Iirc he showed 3 SAT (NP problem) and reduced to Traveling salesman

[@crustbukkit]

I would like to get rich quick, this is why I chose to become a painting major. Never mind u said math.

[@justarandomf-4gphantom170]

No. Please go into German politics.

[@youngrex7694]

@hi there What happing in German politics, aren’t y’all rank high for the least corrupt governments

[@Vaaaaadim]

@@youngrex7694 The joke is a reference to the fact that Hitler wanted to become a professional artist but he failed the entrance exams to some art institution.

[@drawdo2905]

Sam sounds like he solved this equation.

[@backdoorgate]

The ad that played before the video just fit perfect

[@ggandalff]

Nice video, but actually, the TSP is NP-hard but not NP-complete. It only becomes NP-complete when you turn it into a decision problem, eg "Is there a route that costs less than X?", which is easily verifiable inP time (in the original problem, the only way to verify if the route that you have is the shortest one is by computing every other route) Correction: I messed up, I somehow missed that the way you phrased it was the decision problem, so It's all good

[@joshuazelinsky5213]

They did phrase it in terms of whether or not it was shorter than a specific distance, so they are all good.

[@ggandalff]

@@joshuazelinsky5213 You are right, I somehow missed the way they phrased it

[@jorns6678]

Even this knife you will replace after a year. Learn how to sharpen one, and your 20 dollar knife will last a long time

[@tylerlackey1175]

The only video without shilling in the first 10 seconds has a 20 second long rant written by a redditor

[@KHTangent]

I feel called out (2:09) But I did not notice any mistakes at all, good job on this one :)

[@elmacho2789]

I was gonna quote that super long sentence at the beginning of the video and then make fun of it. But it’s literally so long to quote. I just can’t. 😂

[@LakkiTunrung]

_Hey, psst-do you want to get rich quick? Have you exhausted all the other get-rich-quick schemes on the internet?_ _Do you have absolutely no marketable skills because you pursued a degree that became obsolete shortly after graduation due to an unstable and rapidly shifting job market, which then ironically drove you into crushing student-loan debt that compounded with the pressures of late-stage capitalism to create a predatory cycle of poverty that has ultimately forced you to desperately scrape the internet for schemes to support yourself financially?_

[@Potato-km4zg]

P loses because he's alone and NP is two so basically its a 1v2. It's been a while where my 1 million?

[@NoodleProductions]

But what if P is Dream?

[@Potato-km4zg]

@@NoodleProductions He wins for a while then people finds out he used pvp cheats so he loses. Wins at the start but at the long run he losses.

[@aakla]

So P would be a 20% tip NP would be a 20% that took the tip into account of the total so it would keep increasing,?

[@bane2201]

I'll try to explain it - HAI didn't do that well. In these examples, I'll call the number of items X. P would be "I ordered these specific X items in the menu. How much is a 15% tip?". NP would be "My bill from yesterday had the total of $123.45, but that seems high. I forgot what items I ordered, but I know the menu has X items and I ordered 5. Are there any 5 items from the menu add to $123.45?" The first problem requires adding X numbers - you can do that in X time units. The second problem doesn't have a "easy" solution - the best known solution takes 2^(XK) time units. K is a constant number you shouldn't care about here - the point is that each time you put another item on the menu, the number of units goes up a bunch more than it does in the first case.

[@precumming]

The prize isn’t for solving that P=NP it’s for solving P=NP. Slight difference, the first is asking to show it to be true, the last is asking to show if it is true or false. P=NP probably isn’t true so my point is that if you get the million dollars you’ll be able to put it in your bank.

[@Praharshkstudios]

Alright. I need a lot and I mean A *LOT* of pens and paper. Oh, and also like maybe 4000 pieces of mango flavored jelly?

[@rpb4865]

Holy hell! That 4 knives set costs same as my monthly salary here in India 😂

[@Rozenkrantzz]

Your traveling salesman example is incorrect. That's an NP-Hard problem, not NP.

[@fetchstixRHD]

I was going to say that the explanation didn’t make sense to me!

[@lore9625]

His formulation was a decisional problem so it's NP. Also, "your"

[@a_guy7723]

5:30 swiss army pocket knife : amateurs

[@Praharshkstudios]

"-------, Found out why the box has a band-aid," lol

[@ultraviolet.catastrophe]

To clarify, the P versus NP problem is a computer science problem, not a mathematical problem.

[@1vader]

Well, it's theoretical computer science which is pretty much just a branch of mathematics.

[@Xontaro]

P vs NP is a problem in theoretical computer science, which can be viewed both as a subset of computer science and mathematics.

[@ultraviolet.catastrophe]

@@1vader "Pretty much". That's right. In another words, "very nearly". The P vs NP problem is not an entirely mathematical problem. It's close, but it doesn't cut it. That honor belongs to the Riemann Hypothesis.

[@Vaaaaadim]

@@ultraviolet.catastrophe A solution to P=NP would be a mathematical proof. I don't see why it wouldn't count as an entirely mathematical problem.

[@ultraviolet.catastrophe]

@@Vaaaaadim If P=NP will be a mathematical solution, what about P!=NP?

[@MikhailFederov]

I know the scriptwriter wrote this by creating their own ELI5 for themselves, but much of the language used in this video is extremely misleading and wrought with technicalities.

[@pvic6959]

2:08, they knew we'd come and point out mistakes LOLOL

[@kicking222]

I knew what the video was going to be about just from the title, and I STILL don't fully understand it... but you certainly helped make it easier.

[@saucylegs]

Woah, just a few days ago I was browsing Wikipedia and got to the article about this. I didn’t totally understand it so, thanks for this video

[@pinnedcomment8614]

Today I learned: The probability of a blue lobster existing is widely touted as being one in two million.

[@pinnedcomment8614]

Crazy Fact: In 2006, a Coca-Cola employee offered to sell Coca-Cola secrets to Pepsi. Pepsi responded by notifying Coca-Cola.

[@eacalvert]

Good job Sam and crew!

[@JackalBruit]

Well stated sir! &! das from a recent Penn State BS in Maths grad :)

[@moosesandmeese969]

So these problems are like encryption functions. SHA256(data, encryption key) outputs encrypted data It's easily verifiable when you have the encryption key, but requires an infeasible amount of computing power to derive the original data or the encryption key just from the output, even though the SHA256 algorithm is public information. There's no actual proof that you can't derive the input just from the output, but SHA256 is used everywhere for online encryption because no one has ever been able to derive an input just from a given output. Once super processors become mainstream, SHA256 might be broken, but just by increasing the number of bits of the encryption keys, the problem requires exponentially more computing power to crack, something that even super processors can't keep up with. This is also how cryptocurrencies work. Transactions use SHA256 with the input data being the history of transactions up to that point, generate a random output and mining computers guess and check millions of encryption keys with the SHA256 algorithm until they find an encryption key that gives that output, at which point the transaction is verified. Because it's SHA256, it's completely infeasible to try to pull off fraudulent transactions

[@korosheht5446]

Me who fell asleep in the middle of the video then woke up in 5:00 : how tf did math problem became cooking problem

[@branpod]

Teacher: the test will be easy The test:

[@MafiaCow01]

Now I have context for that one Elementary episode.

[@MadXGamer]

Thought I recognised the map at 3:15, a restaurant I used to enjoy going to that sold massive platters of meat and potatoes was there, but apparently it's permanently closed now :(

[@henrytang2203]

You've got a better shot at winning the lottery than cracking these maths puzzles.

[@mathiew_]

5:19 I gotta be honest, that's the smoothest progression I've ever heard.

[@NonTwinBrothers]

Ok let's see how well he really does when trying to describe this Sam, I don't have any expectations in you

[@caspermadlener4191]

There is also another problem with a prize of $1,000,000. It is called Beal's conjecture. The problem asks whether or not there exists three coprime natural numbers a,b,c such that aˣ+bʸ=cᶻ, when x,y,z are all at least 3.

[@vrclckd-zz3pv]

Wasn't that solved? I thought numberphile did a video on it.

[@atzuras]

It's nice you used a map of Barcelona and marked the route from my home to the comic shop

[@delch016]

Got nothing better to do this Sunday so might try it

[@husandeep1826]

0:01 man went rapping 😂

[@themanofquagga]

Wasn't expecting that opening, but y'know I'll take it

[@user-hd6gs1xv5x]

Everybody gansgsta till Sam raps the terms and conditions

[@robotocelots]

Small correction for the TSP. To find an optimal solution you don’t need to check all paths. The most simple algorithm to show this is BFS, Breadth First Search, which always gives an optimal solutions (in a Euclidean space). You could theoretically design a problem where BFS takes the same time as looking through all solutions but it will always be at least as good.

[@piercexlr878]

BFS for traveling over every node does require checking every path. It just generates them in an organized way. And it cuts out repeats that reach the same path by starting at a different node.

[@feuby8480]

I remember being teached this as student. It was a nightmare. And demonstrating that problems are NP-completes is also horrible. This is on the strange part of computer science I really like, but that is a bit too fucking complex for me to have the energy needed to handle or think about.

[@iuppiterzeus9663]

actually, finding the shortest distance between two points can be solved in O(m + n log n) (faster than polynomial time). The TSP is only about the shortest so called "Hamiltonian Cycle" but your graphic implied otherwise. To your credit: Really good (entertaining and understandable) video on a not so simple topic of computer science

[@lucearne1849]

"Thanks for solving the hardest problem in the world." Me : *No need to Thank me*

[@lamenwatch1877]

You should talk about the Collatz Conjecture.

[@LoFiAxolotl]

When you watch a video about P vs NP and you have P=NP tattooed on your shoulder because you're a next level nerd

[@DiarreaChiclosa]

Why do you believe (or hope) P=NP instead of the opposite?

[@anirudhdiwakar987]

You know, I went to the website to checkout this thing, maybe help out our bro Sam here. And the knife that he shows here? That's $134, after discount. The while set? Nearly 4 times that! Maybe it's my country and its high inport costs? I don't know... Still, il keep my $20 knife and sharpen it when it gets dull, use it for a few years and get a new one. Oh....good video by the way. Hey! I've got my priorities okay?!