Это видео недоступно.
Сожалеем об этом.
This Problem Could Break Cryptography
HTML-код
- Опубликовано: 1 мар 2020
- What if, no matter how strong your password was, a hacker could crack it just as easily as you can type it? In fact, what if all sorts of puzzles we thought were hard turned out to be easy? Mathematicians call this problem P vs. NP, it is perhaps the single most important question in computer science today.
Go to Brilliant.org/S... to try their Computer Science Fundamentals course. The first 200 subscribers get 20% off an annual Premium subscription.
Hosted by: Hank Green
SciShow has a spinoff podcast! It's called SciShow Tangents. Check it out at www.scishowtang...
----------
Support SciShow by becoming a patron on Patreon: / scishow
----------
Huge thanks go to the following Patreon supporters for helping us keep SciShow free for everyone forever:
Kevin Bealer, Jacob, KatieMarie Magnone, D.A. Noe, Charles Southerland, Christopher R Boucher, Alex Hackman, Matt Curls, Adam Brainard, Scott Satovsky Jr, Sam Buck, Avi Yashchin, Ron Kakar, Chris Peters, Kevin Carpentier, Patrick D. Ashmore, Piya Shedden, Sam Lutfi, charles george, Greg
----------
Looking for SciShow elsewhere on the internet?
Facebook: / scishow
Twitter: / scishow
Tumblr: / scishow
Instagram: / thescishow
----------
Sources:
mathvault.ca/m...
www.cs.cmu.edu...
stackoverflow....
www.cs.ucc.ie/~...
news.mit.edu/20...
www.scottaaron...
www.scottaaron...
people.cs.uchic...
Go to Brilliant.org/SciShow to try their Computer Science Fundamentals course. The first 200 subscribers get 20% off an annual Premium subscription.
I feel like p would not equal np cause there two different things. Like saying a red blood cell equals a human. Now one blood cell could have all the DNA and information needed to describe a human it does not equal the trillions of dif cells to make a human
1/0.....do I win?
Ok
3:09 that's fallacious. It's not 2^25, it's the entire permissible character set of the password system to the 25th. If it's 2 (A or B), that's not a dumb password, it's a dumb password parameter system. If you chose that password from the entire ASCII printable character set, that'd be 95^25. Significantly more secure.
Be prepared ,
I broke rsa 280 in just 5 minutes!
No matter what you think!
"the thing computer scientists care obsessively about is SPEED"
Ah yes, good old amphetamines! Nothing like spending 18 hours coding while erm, *medicated*.
🤣🤣🤣
Lmfao I'm on it rn
username checks out
Speed, indeed.
Helps you cope with the time it takes to do or fin anything or even switch your device on - having grown up with early devices like an Amstrad 464. Switch it on - friendly blue and yellow simplicity. Put tape in deck & type a word or two, listen to the comforting funky loading screech ¨music¨, and then play. Without buffering or any such. You can spend all night with stick men and tabulated facts and the roar of he crowd, with original football manager. But it is very different.
_I don't need any fancy decryption techniques._
_I have_ *_Brute Force._*
Brute Force this! *Restraining order*
👏
with that muscle you can get password through extortion
Username checks out
You're a fake
*clicks on video*
me: 'what is this gonna be the p=np video'
hank: 'this is about the p vs np'
wow that itsec degree really doing wonders
Computer scientists after discovering that P = NP:
_I am speed_
Haha
::Flash music intro plays:: "My name is Barry Allen..."
@@Monkeyb00y you spelled lightning McQueen wrong
As a person with a degree in computer science and a teacher, I must say this is very good layman explanation of P vs. NP and the examples are very life-like.
I feel like I've been clickbaited. I thought the RSA algorithm was cracked!
Me too, bro. So all of this to say "nobody actually found anything yet, they just put a prize on proving the theory that speculates that maybe someday it could perhaps be possible".
Guilherme Mauricio thanks for saving me time.
Yeah, pretty much just clickbait. "A problem that would break cryptography" wouldn't be as misleading.
One should note that the RSA algorithm is already "cracked" for quantum computers via Shor's algorithm. A scalable quantum computer which could run it for common key sizes doesn't exist yet but there will probably exist one in the next decades. Probably long before someone proves that indeed P≠NP.
Such a proof wouldn't help anyway because we already know that breaking RSA lies in BQP (the quantum computer equivalent of P) which means that it can be solved in polynomial time on a quantum computer.
That being said, there are already some proposed alternatives to the RSA algorithm which do _not_ lie in BQP, which means that scalable quantum computers are not a threat to online security. At least as long as they are really some time away so that we have time to switch the worlds communication infrastructure away from RSA.
The only really bad news would be if really P=NP. But this absurdly unlikely. The "empirical evidence" for P≠NP is overwhelming, both according to common sense and according to well-known experts like Scott Aaronson.
Trurl , excellent comment on Shor’s algorithm. I was about to write something similar but, luckily, found yours. The quantum apocalypse will happen sometime in the next two decades if Moor’s law holds for the number of stable Qbits. However, IMO the threat is not to encryption but rather to digital signatures. Much very good work has gone into quantum resistant hash based signatures but, sadly, transitioning to them will be hard and mass transition will be ignored till the last min.
Having dish soap on the list twice will surely screw up the algorithm.
Dish soap
dish soap
dishsoap
dishsoap(1)
Oh
which is why you should exclude any found items on the list, making it take less time each loop. not really the best example.
How do we know the first one isn’t fish soap? Phish soap? Perhaps wish soap?
Not with good randomness.
• 5:57 - Um, that's a loaded and specious statement. Even if P=NP, that only means there _should_ exist a _relatively_ (6:44) simple solution for any given problem, but it doesn't just automagically give it. Someone would still have to try to figure out an efficient solution which may never even happen.
• 6:18 - Quantum computers are a much more practical and likely threat to passwords than P=NP.
If the memory of my college algorithms class serves me well, all problems in P can be solved in polynomial time by converting the input to that of another problem in P, solving that problem, and then interpreting the output to some answer to your actual problem in poly-time.
If P=NP, then by virtue of this property, any NP problem can be reduced to a P problem in this manner. We're still boned in that case.
@@FeralPhilosopher If P=NP were proven by contradiction, instead of by induction or a direct construction approach, it might not yield an obvious algorithm, even though it would imply that one exists, though given that most complexity theorists seem to think that P=NP is unlikely, it's probably a moot point. 😅
Quantum computers aren't a threat to passwords. They're a threat to certain asymmetric encryption techniques that require prime factorization. P=NP isn't even a threat to passwords, this video is wrong. It would be true if a malicious attacker could actually check if a password is correct, but they wouldn't be able to. Only the system they are trying to break into can check if a password is correct. It is an NP problem only for the server that can do the actual checking.
I was ready to write the same comment. Let's assume P=NP is proven by mapping a 3COL Problem with N nodes and E edges to a natural number b is such a way that b is prime if and only if the original graph is paint able in 3 colors. Let's further assume that b consists of at most N**10 * E**20 digits.
This would be a prove for P = NP. PRIME is already proven to be P, and 3COL is NP-hard. However, PRIME is already an example where the polynomial algorithm is not used because it is slower for all inputs that we can solve in reasonable time. It will be faster for these absurd numbers in this hypothetical prove, but it'll take years to check a graph using this transformation, while brute force will be faster for almost all graphs except very, very large ones. And does anyone care if I'd announce right now that I found a revolutionary new method to crack passwords longer than 1 billion digits? I wouldn't.
@@bisaVCI you got me there lol
I feel like I've learned something but I can't tell you what it is.
I felt the same
Mildly misleading implications in the thumbnail, I thought for a moment that someone actually solved the P vs NP problem.
just off the thumbnail i was concerned it was a breakthrough in quantum computing, 'the ultimate brute force approach'
Always keep in mind that SciShow is not really targeted at specialists ;)
Great introduction to the problem for laypeople imo!
I'm trying 😁
It has been proposed that even if you break encryption somehow the first time everything collapse might take time since even linear time might be too long for the size of the input. However let's be real for a moment most likely p!=np, otherwise a lot of things break
Edit: Lol haven't finished the video, my comment is kind of useless.
agreed. was searching the captions for 'quantum computers' or just 'quantum' but... it should read P vs NP, in which case you don't search for the obvious answer. Also: 1 lousy milion dollars for the key to all encryption? You've got to be kidding...
2:08 No Patrick. That isn’t mayonnaise.
Hank, his name is Hank.
@@BengtRosini13
I'm fairly certain that it is a spongebob reference.
I believe I've seen that name and profile picture before...
@@HavocLoods Have you seen mine? I was there when you were born.
2:17 "to some exponential power" ah yes, as opposed to non-exponential powers...
Yes, for example UNLIMITED POWER!
JNCressey maybe like a negative power??
or to some constant power?
as opposed to other powers, such as 240VAC powers, presidential powers and dictatorial powers
@@jongoodenough3162 And "fightthe" power!
Tl;don’t watch: There is no threat to cryptography.
It’s just a video on the P=NP problem with a clickbait title and even more clickbait thumbnail. I expected better of SciShow, and thought they’d actually be reporting on some breakthrough. I regret that leaving this comment counts as engagement on the video.
I thought the same thing. We have mathematical proof that time travel is possible, but that doesn't mean that we can do it. We know how to build a space elevator, but we don't have the necessary materials. Fusion power is possible but not practical. I expect better from them than this.
And you didn't see what was dangling in your face...
Cryptography has existed for millennia. I don't think it is going away anytime soon
Thanks, I wish I had read your comment before bothering to watch just to make sure there wasn't some recent breakthrough.
As a matter of fact, quantum computing is working to make that problem more accessible, if I'm not mistaken. I thought for a moment that they were going to speculate wildly on "the future of quantum technology". But not even that. Disappointed.
I really liked how you explained this is such a simple way. I'm not a person who is very knowledgeable about algorithms but I was able to follow along with this and understand!
I've always had a decent intuition for math and physics and can usually follow along with videos from channels like PBS Space Time, 3 Blue 1 Brown, Numberphile, etc. But P vs NP has always been something that didn't come naturally to me and I struggle to grasp the concept. This video is the first that I've watched that left me feeling like I learned something rather than just being more confused. And that's why I love SciShow and all its sister channels.
now let's work on your haircut
I was almost certain this was about Quantum Computing. There's another area that threatens to decimate cryptograpgy. If they ever do manage to get Quantum Computers streamlined... well, you've heard "we're doomed" too many times lately anyway.
So far, quantum computers (in theory) are only good at one type of cryptography. Granted, discrete logarithm based systems are used in a LOT of places, but certainly aren't the linchpin holding everything together.
@@infinite1der As far I understand public key cryptography uses mostly RSA and RSA can be attacked with quantum computers. Which comes close to "holding everything together". RSA can be replaced with alternatives which are immune to quantum computers but this takes time. Luckily, developing scalable quantum computers will also take a lot of time, hopefully _more_ time than replacing RSA.
Wouldn't one of those "Five attempts before you're locked out for an hour" have a big impact on this kind of brute force attack, no matter how fast the algorithm can turn out guesses?
if a person gets hold of the system any attempts constraint is very easily bypassed. An encryption algorithm should be strong even if the full details are in the hands of the attacker.
Yes. But in some (maybe most) circumstances, if someone guesses a secret he can easily verify it completelt by itself. For example, if i try to guess an encryption key, i can try and decrypt some communications and check if i get something that makes sense or random garbage. If i get something that makes sense i guessed the right key. And i can do that completely by myself, without interacting with the parties that are trying to communicate privately.
@@noamtashma2859 Thanks that is exactly what i wanted to say. My english was not good enough to properly word the concept.
The problem these days is that people manage to lose laptops or get hacked losing the password list in the process. Now it doesn't store the actual passwords, but a cryptographic digest of the password into a fixed-length piece of data called a hash. The only way to crack these password hashes back to passwords that can be used on other websites is to guess and check, so if the guess step is slow enough it becomes impractical. If, on the other hand the hash could be reversed into a a list of passwords that get digested to that hash, then the computer could just look for the shortest one that's not complete gibberish and send it along to log in to your bank.
You're putting the vulnerability in the wrong place. The vulnerability here is when someone *else* types in *their* password, and you pick up the gibberish they actually send. Since the remote computer has to know what it's getting, it has to send unencrypted instructions to the local computer on how to encrypt it; if P = NP, those instructions would also let you decrypt it. Even if the algorithm discovered isn't feasible, its existence would mean that probabilistic algorithms would be much more feasible.
shoutout to everyone who works with software and had a mini heart-attack
I felt clickbaited.
Hmmm win a million dollars from some science price vs selling the masterkey off to the highest bidder for upwards of billions of dollars...hm....
Use the master key to slowly change the structure of human society over decades just for the fun of watching it happen
Proving whether or not P=NP isn't a masterkey for the destruction of crypto though. The proof isn't an exploit.
@@themorebeer3072 The soul always screams for mercy, but finds naught but the huntsman's axe.
The proof might not give you an explicit algorithm to do it
Yeah, that's pretty silly. The implications of such an insane feat would *far* outweigh a measly 1 million dollar.
Why would I take one million if i can hack my way to a billion
Because then you got future kids who got to learn what you discovered thinking "Another math rule some donkey called after himself."
@@RaptorTwitch so you think mathematicians are donkeys 😶
For the same reason you pay for your groceries in stead of shoplifting.
@@ze_rubenator So, you just assume everyone follows your code of conduct?
@@RaptorTwitch very rarely do mathematicians/scientists name something after themselves. It's the following generation or generations that rename it
Love the topic! Some more illustrative diagrams would have really helped grasp the math, though
hacking my account would be a waste of time, for all of my 0.42 cents...
I'd pay someone to hack my bank account bc I forgot the password 😅 (and all the other stuff except the email address that's attached to it *is utter fail*) so I can't access my account online. A big problem bc my bank refuses to do anything in person. It's online or pfo. *sighs*
Sure, but your account is worth a lot more on its own than just the money inside it. Your identity, and the ability to funnel other financial transactions through it makes it worth the effort. All the while, your name starts being associated with shady deals, and with some bad luck you'll be the one to end up in jail. Don't assume that because it's not worth much to you, it isn't worth much to a potential attacker.
Well, look at Mr. Moneybags over here bragging about his wealth. Better be careful or someone with less money might kidnap you and ransom you off for that fat stack of coins you got there.
We'd love your two cents on this topic, but apparently, you can't even afford that.
43 cents - currently
i love the implication that this person's impulse buy is...a can of soup
Its expensive soup
PP vs. No PP
PP vs pp
I mean PP is actually a pretty powerful complexity class. If I remember correctly, I think P^PP contains PH.
This is a really big problem. But all you gotta do is call Bob The Builder to fix it, He can fix it in a millisecond. Like a snap of a finger
Concerned officials:
*What if we already called and it didn't work?*
Bob is God
Sid the Science Kid... or Count Dracula....
Thanos can fix things with the snap of a finger too
@@smort123
Not if he can't snap.
This reminds me of that article that showed Magic the Gathering to be the most complex game in terms of computer science and game theory. Basically, there can be no winning algorithm for determining the best play in MTG. The best thing about it is that they proved it by creating an entire Turing machine using only the cards from the game. That's right, they made a computer using cardboard cards. And because of that, they were able to determine that winning the game is much like the halting problem, wherein it is hard to determine whether a computer will stop the operation or will continue forever.
I have a simple proof that P=NP but this comment box is too small to contain it.
Send me a pastbin link then
Is this your last theorem?
@@MichaelBrodie68 No- it's my Little But Just Too Big For Comment Box Theorem.
P=MP .. If you look you'll find that i r the solution.. and Published in a small box. Now where is my Hand?
That's a PIMP Pi.. if I ever saw one..
Hank 2020:
Discovering and finding out new things is the best part of science and also being alive, and if the result is in our favour that would be nice too.
The FBI have a hard time breaking into an iPhone that has only 6 digits for a pin code. The trick is that Apple only let’s you try your password 10 times before it locks the phone for good. Saying that brute force can defeat this kind of security is just wrong. If your pin is somewhat random and no one watches as you use it, you are probably safe.
This can also be simplified to a search algorithm which can be incredibly tempting to attempt. If you’ve got an algorithm that finds the minimal route with specified cities visited and arrive back at the same spot without going over the same road twice and you can guarantee this in polynomial time then you’ve solved p = np. Unfortunately in practice it’s not so easy
Brilliant explanation!
Btw,
1) while polynomial time is the most popular, other definitions of "easy/fast", it is just one of many studied ones.
2) For practical applications, N^2 is already bad. If you actually have to compute something, "easy"/"fast" means N^1 or let's say about as hard as sorting a list. Unfortunately, that definition is even harder to study.
I'd argue that if P = NP passwords would be useless.
Doesn't matter how hard it is to check/recover it *as long as checking is faster than recovering* the password.
If the difference is subtle then a new password could be generated mid-session as needed. If, however, P=NP, an attacker would know the password by the time as the server would check it.
No, even in polynomial time it could easily take you longer than the universe existed. The realm of P is huge.
Assuming 25 items in a list and 25 items in a cart, assuming that matches are removed, the sort get quicker with every item.
Example:
Randomized sets of A-Y and 1-25 where 1=A, 2 =B etc. Both sets get smaller with every match. so you start with 25^2 but end up with 1 after 24 iterations. You can even ignore a bunch of options per iteration. Select Random letter (C), compare to list of numbers until you find (3) you will check at most 25 times. Select next Random letter (E), compare to list of numbers at most 24 times... etc. This gets quicker still with an index. "I remember seeing 17 on the list about here, Ah! There is is!"
Also se "The Basics" with Tom Scott for more on this.
To the people leaving comments about this being click bait a quick look at the about section will reveal the schedule that clearly states when the videos with news go out. The tittle and thumbnail are definitely clickbait but you have to remember that scishow is not a scientific journal it is a RUclips channel
As someone who studied theoretical computer science (complexity theory and other things) in college, is just like to say that the notion that P=NP is almost unfathomable. The interesting thing about the PvsNP problem is how something so seemingly obvious has evaded proof techniques for so long (and probably will for a long time to come). But still, great video!
A) this is why the security server only gives a finite number of incorrect tries. And b) this is why they annoy everyone with 2 factor verification. It takes more than just the correct password to get you in to secure sites. Chances that a hacker has both the correct password AND access to the cellphone you have set up to receive the multifactor BEFORE that multifactor key times out are slim.
Just to be complete, proving that N=NP would not immediately break all encryption. It would just prove that there must exist an approach that would quickly solve the NP problems. Finding that solution could take another 200 years. Also many of these computer science mathematical proofs only exist in math, they are just not feasible in real world. They involve wacky things like machines with infinite 1 dimensional memory. Useful for mathematical proofs not so useful for building a computer.
Another case in which P=NP wouldn't break encryption immediately would be if the proof is not constructive. If the proof just tells us that indeed both classes are the same, but it doesn't give us an example of a polynomial time algorithm for an NP hard problem, them current encryption methods are safe until one such algorithm is found.
My first tattoo was P=NP on my wrist after I finished my CS degree. It's in a decorative type face since I consider this the Holy Grail of Computer Science.
Thank you for this video, now I can send people here when they ask what it means.
Kudos for being able to explain this problem.
BTW...
shopping_list = [item1, item2, item3, item4]
def grab_item_from_shelf(item):
if item in shopping_list:
shopping_list.remove(item)
return True
else:
return False
So all of this to say "nobody actually found anything yet, they just put a prize for someone who proves the theory that speculates that maybe someday it could perhaps be possible to break cryptography"?
I think quantum computing will get there faster.
I think your description might be misleading people; at least as far as modern encryption goes. Passwords are used for verification purposes; they prove that you are who you say you are. Encryption is about securing your communications. When two computers establish a secure connection, they share/determine a key using asymmetric methods, or else they encrypt everything using asymmetric methods. Either way, breaking these asymmetric methods are NP problems.
Are there proposed solutions to any NP-Complete problems (if so, will this P vs NP question remain important in a post quantum world)?
If P=NP, then just because it means that a fast solution exists for any problem, doesn't necessarily mean that we will instantly know the solution for every problem? As far as I understand we're comparing how different algorithms scale - that doesn't mean they are the same algorithm. E.g. I can say there's a sorting algorithm with time complexity O(n log n) but saying this doesn't tell you how. You'd still have to think of the exact way to do it (or google it like I did). But there's a difference, right?
Others have mentioned this fact, but even if you show P=NP, and that the solution is fast, you don't necessarily have a way to find those fast algorithms. The key would be finding a constructive proof of p=np, otherwise all you have is the knowledge that someone somewhere*might* have figured out a fast way to break your password. But that's currently true with current technology.
So Hank can place 25 identical items in his cart, and as long as it is on his list, his algorithm will say he was successful in his shopping.
Got it.
Soup-check Jar of white stuff -check.............................
That is how to win at shopping.
Computer science explained through a bar analogy:
programmer is crash testing a bar. He has a test customer walk in and ask for 1 beer.
He has a test customer walk in and ask for -1 beer.
He has a test customer walk in and ask for asdfjkl beer.
He carefully programs his bar to handle all these cases, and test for error situations accordingly.
The bar opens.
A real customer walks in and asks to use the bathroom.
The bar catches fire.
The proof that P = NP would not necessarily break anything. If the proof is non-constructive for example - meaning we can show both classes are equal, but not provide a method / efficient algorithm to solve them - we'd know that there is an efficient solution to factorizing or the discrete logarithm problem but we'd still have to find it and nobody guarantees that we ever will.
We all know P is for Pirates and NP is for Ninja Pirates, and Ninja Pirates are still Pirates, thus making P=NP. This is especially scary for cryptography because Ninjas have mad hacking skills while Pirates love stealing, and Ninja Pirates have plus 2 to dual wield short steel cutlasses which hack more and cut less, while they steal and hack with less short cuts...
Give me money, science...
Even if P = NP (which is doubtful) all that does is say there is a faster way than to do a brute force check of every possibility. It doesn't provide any clarity as to what that faster way is, or how much faster it would be.
A P order solution would still at the very least match the complexity of the original problem.
The grocery example is not terrific... It's linear! You have to compare 2 lists. To do that: sort them (linear with bucket sort) then just check (linear).
Finding a solution to P = NP does not break encryption; someone (or something) still has to find/write the algorithm to solve your password, or break the cipher, or solving discrete logarithms (see also Shor's Algorithm). Just because we know a solution exists doesn't mean we know how to solve the problem.
I already knew the p vs np problem but you all did a great job of making it accessible. That could not bad been easy, so nice work
A million dollars is for this field a drop of water on a hot stone. I have an algorithm which breaks RSA security in a matter of seconds, but I will release this information only to somebody who, de facto, will generously solve my struggle to survive decently. Such an information is worth an in-estimated amount of money and in the same time, it's just worth what it really is: ten lines of easy to read and to understand instructions, a developer and a normal PC. Knowing a solution to a problem does not remove poverty, but it helps to keep dignity.
Organise your grocery list alphabetically
Then compare your items to the item in the middle of the list
Then if its G (garnish) you fold the list in half and check the top
Then rinse and repeat
It's perfectly possible that someone proves that P = NP, but if the proof is not constructive there may be no way to derive an algorithm that finds the solution from the algorithm that verifies it, i.e. we prove the algorithm exists, but we don't know what it is.
The thing is that even if P does equal NP, that doesn’t guarantee we will be able to immediately find a good algorithm for it, as polynomial algorithms can still be intractable.
Ie, with what I’ve been learning about in Discrete 2 covering this topic recently, even if we find a polynomial way to solve an NP-Complete§ problem like PARTITION (given a set of positive integers, determine if there is a way to divide it into 2 sets that sum to the same value, like 1-2-3-4 being 1-4 and 2-3), we could theoretically solve such a problem by doing a series of transformations into inputs from other problems, but it would end up with a ridiculously gigantic mess of an input to PARTITION that would probably still be unreasonably long to solve. We’re still going to need a way to work smarter, not harder to break crypto.
§NP-Complete problems are problems in NP such that an input to any other problem in NP can be transformed into an equivalent input to the NP-Complete problem in polynomial time; if there was a way to solve such a problem in polynomial time, then you could solve all problems in NP by reformulating them into an equivalent input for it and solving, so P would equal NP. For example, the Cook-Levin theorem uses another definition of NP to show that SAT (given a Boolean formula, see if there is a way to set the variables so that it evaluates to true) is NP-Complete, and from that we can then reduce SAT to other problems like CLIQUE (given a graph and a number k, see if there are k nodes in the graph all connected to each other) or SUBSETSUM (given a set of positive integers S and a target t, see if there is a subset of S that sums to t) to show they are also NPC.
It is not 25 squared... it is actually 25+24+23+...2+1 or up to 325 checks. Once an item has been checked then it can be removed from the list so the next item only needs to check against a list of 24 items, etc.
I have an encryption method that nobody can crack. The only problem is generating the keys is kinda a pain. That being said; when you have a key you won't need another for a long time (they're just that long)
Man, jigsaw puzzles will be ruined. Thanks, math!
The only way P = NP is if N == 1 or 1^n where n = 1 to infinity. N cannot be negative or 0. N also cannot be a float or real number because N = P/N and P = NP at the same time. Let N == pi and it clearly won't work. Therefore, we can rule out: N == negative, 0, and real numbers. N must be a positive integer and it must also be 1 or 1 to the power of n.
Thinking about it further, N could also equal i or imaginary. The point being that the possible numbers for N are restricted.
I saw the title and was like "wait a sec, i'm a CS student and i didn't hear any news about something like that, is quantum computing this advanced already and i never heard anything about it?"
Then i opened the video and "Oh, it was just P vs NP"
Thumbs down for the alarmist/click-bait way I was lead here. You are better than that.
And you're better than that pfp. That little tiki doll scared my mom horribly when she was a kid, so she decided to show me when I was a kid to see if it scared me too. Turns out I have a genetic fear of dolls with knives
yeah, but they ended up not doing a bad job at explaining!
@@RustyShackleford051 "Trilogy of Terror" if you want to relive it. But trust me, you'll be fearing couches again even as an adult.
@@frac I think I'll pass honestly lol Either I'll be a terrified grown man or the mystery will be ruined ya know
I need to remember this video for the next time I need to explain P vs NP. (Comes up surprisingly often.)
Ack, can't we agree that checking items in a grocery list is run time nlog(n) ?! I don't know about you, but once I've found the mayo on the list, I don't plan on continuing to check to the end of the list, meaning it's faster than n^2.
@1:01 to understand what P and NPR and why people care so much about them...mainly because the news on NPR is a lot more interesting.
2 part authentication such as logging in using an embedded on screen keyboard to enter a password, to have a random secondary code sent to another device that must be entered within 5 minuets, along with locking an account for 24 hours after 3 incorrect attempts means it would still be difficult to get into some accounts even with the best technology. You could also go old school Vietnam style radio encryption where once the devices are synced, they change encryption every few seconds, so by the time encryption is cracked the radios are already using a new algorithm, a new key, and a new time delay until the next change.
But automatically switching the encryption style must also be 'crackable' in that you can predict what the next one is, unless some human is creating novel algorithms every few seconds. Besides, these attacks are usually done offline, not against a live machine that ratelimits your requests or boots you out after X failed attempts. The scary part is where you've leaked all your password hashes and/or 2fa secrets (encrypted or not), which happens way more often.
P vs NP is itself an NP problem, if we do eventually solve it it'll probably require such a leap in computational theory that the very algorithms used to find the solution would generalize to other NP problems and therefore in and of themselves prove it true. But if P vs NP is false, we'll probably never know for certain.
Some inaccuracies in this video. For instance, the set P is in the set NP, since if a problem is solved in polynomial time, a solution to this problem can be also verified in polynomial time. The set NP does not only contain problems that are hard to solve but are easily verified, that category of problems is called NP-complete.
I remember a security teacher saying that if any of us ever figure out P=NP we should immediately go to a teacher we trust to check our work and either A) tell us what we did wrong or B) have a witness incase something happened to us. If he ever found out that someone had solved P=NP he would either kill them and destroy all records of their work or withdrawl all his money in gold and relocate to a remote island because the world is about to explode.
Nice overview of the P vs. NP Problem, which is unlikely to be solved any time soon.
There's 8:08 I'm not getting back.
Sorry to say: quality seems to be dropping.
I agree. I noticed that 2 channel seem to be dipping in quality. "Today I Found Out" & "Project Veritas". The former is actually recycling content with a new label.
In this video, I benefited from an explanation of P & NP, but I can see how others won't benefit.
You just didn’t get it
Idk, SciShow's other videos recently have seemed just fine to me. The production quality has never been high just due to the nature of the show (daily, bite-sized videos). I admit, I'm not a fan of clickbait. At all. But I don't see how there's been any sort of drop in quality recently.
MrEkShun maybe he’s comparing to crashcourse
"What if ... a hacker could crack [your password] as easily as you can type it?" - Joke's on you, Hank; my password is a pain in the ass to type in xD
To put the difficulty of solving P vs. NP into perspective: it's easier to show how we *can't* prove it than to actually prove the darn thing itself. In fact, *three* different ways have been shown to be completely useless to approach this problem.
Think about that for a second: no matter how you constructed a proof, if it falls into one of those three categories, there's no way you actually answer the question of P vs. NP. And we're talking about fairly broadly and abstract categories, like diagonalisation (used to show for example that there are problems which no algorithm can solve; this is called the relativisation barrier), or using circuits and their size (the naturalisation and arithmetic barrier). And at least the former is a staple when it comes to classic computer science theorems. So in order to solve this, it will take really big mathematical "guns" to tackle this (or it could be as simple as giving an efficient way of solving Sudoku).
It’s quite difficult to grasp the concept that there could be a different way of approaching these math problems by ““checking“the solution as the first step, when you do not know what the solution is. Where do you even begin? With brute force, it’s simple enough. But how do you begin by checking the correct solution? What input do you use?
Technically, if an algorithm is faster than P but you can verify a solution in P time, it's called NP-complete. If it takes more than P time to verify, it's called NP-hard. The P vs. NP problem really is about NP-complete, not NP-hard. Is there a way to reduce an NP-complete problem to a P problem by leveraging the P time verification? There are ways to do this to reduce a factorial speed problem to an exponential speed one. But going from exponential to polynomial has proven to be not as fruitful.
I don’t understand one thing - if someone shows that P = NP, how does that miraculously tell us what the fast algorithms are? How does that break the encryption other than show that it is possible?
Encryptors: Haha, you'll never guess this 1000 digit long prime number!
Quantum Computers: *hold my exponential processing power*
How do hackers check if their code 'proposal' is correct?
Lets take an alarm keyboard with 10 keys:
To disable the alarm you will have to enter 5 numbers.
The easy way to make life hard for hackers is to disable the keyboard for 2^^n seconds every time a wrong code is entered, - where 'n' is the number of wrong codes entered.
Then the time used to test the code is exponential.
The same method can be used by banks and other online services to prevent the hacking test to be performed.
--
Tell me if I have got something wrong
/JD
I don't understand how proving P = NP would suddenly break cyber security. It's not like the theory has stopped anyone from _trying_ to break encryption, and so far no one seems to have done so. How would knowing that encryption is breakable give anyone with the wrong intentions the actual information they'd need to, well, break it?
Increasing the exponent in a Polynomial time algorithm will not generally be useful for cryptography. First, results won't be easy to check as they are today, and second, it's just an arms race. P-time problems of some specific exponent are either easy or difficult based on the capability of computer speeds at the time you are making the easy/difficult judgement. One implication of this is that it's possible, if not likely, that someone can come up with a machine or technique that optimizes the particular degree of exponentiation that you are using for security.
But NP-time problems are (seemingly but unproven) difficult no matter what. NP problems are orders of magnitude more difficult than P problems. We're talking "number of particles in the universe"-degrees of magnitude *of difficulty*. Unless P=NP, then only fundamentally new computation methods, such as Quantum Computers (maybe), can speed them up.
Finding P=NP might be an issue short-term for cryptography, but it would be *insanely useful* as well. What we want to be true is largely irrelevant, but - hope for P=NP. (Having said that, my gut says P != NP and that's just how it is)
Agreed, just because we can't see past the horizon of the direct impacts we even know of, doesn't mean concluding P=NP would be bad overall. My gut also says P!=NP, but one can 'hope'.
Just to add 2 cents: it is not the case that there are 2 answers (P = NP or P != NP). One possible (and quite probable) solution is that it is undecidable.
You should make a correction towards the end.
You said if p=np then that would unlock a fast way to solve problems.
However, it is very possible that we prove p=np but do so non constructively and never find the efficient algorithm.
Its also possible that the "efficient algorithm" is like a monstrous billionth degree polynomial time algorythm, which is only faster than the exponential time one for absurdly large values.
Edit* I'm dumb and probably should have finished the video before commenting. Whoops.
Get those views and write "P vs NP" in the title, we want you to get the sweet ad revenue. :P
"An infinite number of unicorns sitting at a rainbow table snorting crack....."
*sees title of video*
*sweats*
video: *talks about P = NP problem*
me: *relief*
”But if it takes a second to make one password guess for a password that’s 25 characters long, you could be guessing for over a year”
Uuhm, try 70409882332900000000000000000 years if you’re only allowed lowercase a-z in your password...
its kind of rotating lock works,
its need the right number for the start then it stop,
its mean, Check and if guess are true then lock it, move into next character do same thing over and over again,
until all character has been guessed.
its will be fast if the program inside that having system check for each characters we inserted
Take a shot every time Hank says P and Double Shot for NP 🤣
Nit picker here. Shouldn’t it be „exponential time-complexity“ rather than „exponential-time complexity“?
If it is proven that P = NP it still does not mean the algorithm for defeating our current cryptography will be discovered at the same time. But it would be scary knowing that someone could discover it in secret while we cross fingers and hope someone wil not find it.
The real question is WHY would P = NP? They both ask a different question so why would they be required to be the same? The million dollar bounty is to try and prove why they always equal each other but if they don't have a requirement to do so then why would they? It's like apples and oranges just because they grow on a tree doesn't mean they are required to be anything alike. There might be some equations that just so happen to equal each other but I think they would be the exception.
We believed e=mc^2 (yes I know it's not the whole equation) was true unit we found out it wasn't so any equation can be produced to fit any particular view point untill proven.
The thing that keeps irritating me about this is the thought that proving P=NP is an automatic doom for current cryptography. Such a proof, however unlikely, would most probably be non-constructive which means it will not entail a universal algorithm for finding a P alogorithm for every NP one that we have.
Incorrect at 2:33 "A 50 item list ... in which case your algorithm would be much slower." The algorithm doesn't change, which means its speed stays the same. It "... would take much langer.", though :D
As you've correctly deduced, it's "...the execution time of your algorithm would be much slower". It's a simplification in order to communicate the problem efficiently in a few minutes for newcomers, us in the know already understand what Hank means in the strictest sense.
@@crashmatrix this
As a CS student, this is a pretty good explanation for an 8 minute video. No, it doesn't cover all the bases or explain "why" modern cryptography would break, but it's a pretty decent start.
Seems like a problem only a completionist would tackle! Congratulations! P = NP achievement unlocked!
Always purge matched items from your search list. As you progress, your search list shrinks and your processing speeds up.
Great one! I've heard about the P and NP problem many times, but this is the first time I've understood it.
Proving P=NP might not be a constructive proof. Knowing that a polynomial time solution exists is NOT the same as knowing what that polynomial time solution is. An existence proof wouldn't be nearly as impressive. Some digit occurs an infinite number of time in pi (or it couldn't be infinitely long), indeed all of them might, but there's no proof of which one it is.
The time complexity we measure in big O notation by the way. A better example would be the travelling salesman problem.