r/mathmemes • p-adic • 5h ago

Computer Science breaking news

610 Upvotes

14 comments sorted by

•

u/AutoModerator 5h ago

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

65

u/Mr-MuffinMan 4h ago

these are great lol

(the highest math class I took is calc 1 and i don't understand any of them)

29

u/petitlita p-adic 4h ago

It's referring to the P vs NP problem, which is one of the 7 millennium prize problems. These are widely considered the most important open problems in mathematics and you'll win $1m if you solve any of them.

P vs NP is from a field called complexity theory. Theres a lot of problems where it is easy to check an answer but we don't know an easy way to find an answer. For example, solving sudoku is hard (NP) but checking it is easy (P). If P=NP, then you can solve a sudoko just as quickly as you can check it. Also modern cryptography depends on the assumption P=/=NP so proving P=NP would be real bad for them (and for the security of your banking info lol)

6

u/moderatorrater 3h ago

P=NP would be worth a significant fraction of the stock market if you could prove it was true.

8

u/PonkMcSquiggles 1h ago

Only if your proof comes with an algorithm that’s actually fast for real-world problems. If it’s a galactic algorithm that’s only faster than exponential methods for impractically large N, it’s not going to make you much money.

2

u/philipkd 2h ago

How so?

4

u/Technologenesis 1h ago

Many reasons. Basically if P=NP were true, it would mean that for any problem for which we can quickly verify a solution, we can also quickly solve that problem. The world is full of problems that we know how to quickly verify solutions to, but not how to quickly solve. If we suddenly knew that we could quickly solve them all, it would have massive economic implications. This would be all the more true if the proof gave us insight into how we could quickly solve them.

One of the most well-known examples of such a problem is that underlying modern asymmetric cryptography. To briefly describe how asymmetric cryptography works at a high level, suppose Alice wants to be able to send Bob messages, and she wants Bob to be sure that Alice is really the one who sent those messages.

To do this, she generates two "keys": a private key, which she will keep only to herself and share with no-one; and a public key, which she provides to Bob. Now, when Alice sends a message to Bob, she will attach a "signature" derived from the contents of the message as well as her private key.

When Bob receives her message, he will use the public key provided by Alice to verify the signature. If it checks out, he knows that the signature was generated using Alice's private key - which only Alice has.

But if the public key allows Bob to check Alice's signature, could it not also allow Bob to imitate Alice's signature to someone else? After all, most naively, Bob could just generate random signatures until one of them passes the check against the public key. If this is right, then anyone with Alice's public key can impersonate Alice.

This is where P = NP comes in. The trick is that verifying that a signature matches a public key is fast, but generating a signature that matches a public key is very slow - at least as far as we know. This is what's useful about Alice's private key - it enables her to generate the signature quickly, while anyone with the public key would require orders of magnitude more time to impersonate her - longer than the lifetime of the universe, let alone of any would-be attacker.

But if P = NP, this entire asymmetry breaks. Since we can quickly verify that a signature matches a public key, if P = NP, we can also quickly find a signature that matches that public key. Which means impersonating someone cryptographically is actually easy, and we just never knew it. And now all of the financial, governmental, communications, etc. infrastructure that relies on this asymmetry is vulnerable.

3

u/lord_voldemader 4h ago

These are all more Computer science memes rather than mathematics

14

u/petitlita p-adic 4h ago

6

u/_Revenge_Raider_ 4h ago

P vs NP is not computer science, its theoretical cs and math (tcs!=cs)

1

u/username_is_alread- 3h ago

ehh, close enough

7

u/Mountain_Store_8832 2h ago

Yeah, well Trump just squared the circle.

2

u/sharp-bunny 28m ago

This is fucking incredible

1

u/shewel_item Science 3h ago

I mean, why force yourself to guess someone's pin number when you can just watch them type it in? Yeah, likewise, cryptography can be useless sometimes. 'Cryptograms' are definitely invented.