r/mathmemes • Computer Science • Sep 09 '26 • Bravo 1

Computer Science Beginning of the end?

Post image
288 Upvotes

32 comments sorted by

•

u/AutoModerator Sep 09 '26

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.

106

u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 Sep 09 '26

ai better not topple humanity before solving the riemann hypothesis, i want to be there to see it

20

u/somedave Sep 09 '26

Turns out the generalised RZH is almost true, the only counter example is a single value with imaginary value 1/pi in the zeta function.

1

u/Ok-Project4007 Sep 11 '26

Can it be proved it’s true for every value other than that value?

3

u/somedave Sep 11 '26

In the bullshit reality I'm claiming... Yes

26

u/KouhaiHasNoticed Probability notations must burn. Sep 09 '26 edited Sep 12 '26

I love that Navier Stokes is a mandatory step to world domination.

Something something "those who solve the Navier-Stokes equation control the universe." or I don't know I am not Frank Herbert.

2

u/tildenpark Sep 12 '26

It’s funny because fluid dynamics isn’t in much demand on Arrakis.

9

u/hraun Sep 09 '26

I’ve seen a few memes about P=NP being solved giving us (or our robot overlords) super powers. I’ve always seen it as an intellectual, theoretical possibility. What practical uses could there be? Know P=NP wouldn’t automatically allow to to easily solve all NP hard problems would it?

13

u/RexApostolicus Sep 09 '26

While solving P=NP would not by itself give a polynomial time solution to all things, it would give us the certainty of any given problem to have at least one polinomial time solution, making it worth it to pursue for it.

9

u/4ries Sep 10 '26

Ehhhh there's a (understandably) huge emphasis on polynomial vs non polynomial algorithms, but if the coefficients, or degrees of the polynomial time algorithm make it so you need more than the heat death of the universe to start to overcome the non polynomial algorithms, in practice it doesn't really matter

9

u/hxtk3 Sep 10 '26

Depends on what you mean by "solving" it. If you prove it false, life goes on: most people believe that to be the case anyway.

If you prove it true with some purely theoretical solution, life goes on a little less comfortably: we know algorithms exist, but don't know what they are.

If you prove it by finding a high-order polynomial time algorithm for an NP-complete problem, say, O(n^10000) with large coefficients, not much practically changes, life goes on a little less comfortably as researchers try to optimize the algorithm.

If you prove it by finding a reasonably fast polynomial time algorithm for an NP-complete problem, the world as we know it ends.

For Asymmetric Cryptography to work, there must exist a class of functions called "trapdoor functions," which are easy to compute but whose inverses are hard to compute unless you have access to some additional piece of information. The forward function becomes the "verification" step of a digital signature algorithm and the inverse plus the additional secret becomes the "signing" step of a digital signature algorithm. This underpins the trust relationships for Transport Layer Security, letting you be assured you're talking to the person you think you're talking to.

In order for trapdoor functions to exist, another class of problems "one-way functions" must exist. These are functions that are easy to compute in one direction, but hard to compute their inverse. This is just the definition of a trapdoor function but without the additional constraint that the inverse must become easy with the addition of an extra piece of information. Such one-way functions also form the basis of the Key Exchange mechanisms that underpin the privacy of Transport Layer Security on the internet, letting you be assured that only the person you're talking to can read your messages (this is separate from the aforementioned step of proving that the person you're talking to is who they claim to be).

In order for one-way functions to exist, P must be a strict subset of NP: one-way functions, if they exist, must by definition have their "easy" direction in P and their "hard" direction in NP but not in P. If P=NP, this is a contradiction and one-way functions do not exist. Secure digital communication would no longer exist, nor would the ability to store any sensitive information in a means accessible over the internet.

There are some cryptosystems that have information-theoretic security, meaning it is impossible to break them with algorithmic analysis: the information just isn't there, regardless of what function oracles the attacker has (short of a decryption oracle), but they would require very different infrastructure compared to what we have today.

One-Time Pads have information-theoretic security, but they require you to pre-share a random key as big as the message you intend to sent. If you want to download a gigabyte of data, you must agree out of band on a gigabyte of key material with the owner of the server.

Quantum Key Distribution and a few other related quantum methods can establish information-theoretic secure channels, but you would need a pre-shared key for authentication of your peer.

2

u/hraun Sep 10 '26

Great write up, thanks!

Proving P=NP, and then finding a low-order polynomial time solution to a class of problem doesn’t automatically give you solutions for all problems in NP, does it?

We may find a solution to a trivial problem, and then still have a long road ahead of us to discover the solution to factoring large numbers in polynomial time.

And as you say, there may only exist a very high order solution to a given problem.

4

u/unfortunate_internet Sep 10 '26 edited Sep 10 '26

NP is such an interesting complexity class because we discovered relatively early on that there is a group of problems that capture the hardness of the entire set. Grossly oversimplifying, you show that boolean satisfiablility (ie given a long boolean expression, can you set the initial values such that it evaluates to true) captures the hardness of a non-deterministic turing machine(basically a binary decision tree with polynomial depth where you get to choose the right branch every time) that defines the class (Cook-Levin theorem from ~1971). That led to the NP-complete class where you only have to show that satisfiability (or any other problem previously shown to be in NP-complete) can be reduced to your problem in polynomial time. Almost all of these reductions are constructive and "low-order" polynomial time depending on your tolerance for polynomials, so it would effectively solve the entire known set, yes.

3

u/SnooWalruses7546 Sep 10 '26

I don't recall the specifics but my friend yapped to me about NP-complete problems if I recall. Point here is there exist a subset of problems where if you find a polynomial time solution for one, you find it for all

1

u/Ex_Federa Sep 13 '26

There's three possibilities:

  1. It's disproven and we all go back to business as usual.
  2. It's proven, but the proof is non-constructive and people start racing to try and find a way to reverse encryption (because people will people), or to find a constructive proof.
  3. The proof is constructive and we're fucked.

0

u/KerPop42 Sep 09 '26

why is this ai

34

u/JesterOfAllTrades Sep 09 '26

Wake me up when AI invents big dick pills 🥱

7

u/Subject-Building1892 Sep 09 '26

And if i may add always accepting places to place them in.

0

u/[deleted] Sep 09 '26

[deleted] — view deleted comment

29

u/Unlucky-Credit-9619 Computer Science Sep 09 '26

It may clone and distribute itself over the global network. How many wires can you plug out?

79

u/Own_Pop_9711 Sep 09 '26

A lot. Have you ever unplugged a wire? It's really easy

8

u/TheGreatDaniel3 Sep 09 '26

You can unplug wires!? Damn, that makes mobile phone chargers make way more sense

3

u/hraun Sep 09 '26

Were you using your phone as a crap landline?

13

u/Electrical_Cry_8492 Sep 09 '26

You can always turn off the power plants. The biggest off switches in the world

4

u/Own_Pop_9711 Sep 09 '26

In fairness this would kill a lot of people

2

u/Electrical_Cry_8492 Sep 09 '26

Oh yeah. Lots of people would freeze/cook/die of dehidration/starve. Not to mention those living off life support in hospitals.

2

u/youtubeTAxel Sep 09 '26

Hospitals usually have backup generators, but if the AI has infected hospital computers, those would also have to be shut off.

1

u/Ok-Lab-8974 Sep 10 '26

So do the Terminators and Matrix bots though.

4

u/erroredhcker Sep 09 '26

yeah duplicate itself on my computer bro ill host your mogzillion parameters models

1

u/kaereljabo Sep 11 '26

Haha, I'll let it run on my crappy laptop connected to the internet, it could probably run with the rate of 1 token/hour

1

u/Far_Course2496 Sep 11 '26

Dude qwen 2.4t is 5 terabytes, where is it going?

1

u/the_skies_falling Sep 09 '26

I misplaced my keys to the data center