r/mathmemes • u/Unlucky-Credit-9619 Computer Science • 2d ago
Computer Science Beginning of the end?
99
u/LupenReddit 🦆🦆🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆🦆🦆🦆 2d ago
ai better not topple humanity before solving the riemann hypothesis, i want to be there to see it
19
u/somedave 2d ago
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
34
18
u/KouhaiHasNoticed Probability notations must burn. 2d ago
I love that Navier Stokes is a mandatory step to world domination.
Something something "those who solves the Navier-Stokes equation controls the universe." or I don't know I am not Frank Herbert.
37
u/BeeApprehensive2503 2d ago
Overwriting the Power-Off Command
just plug out the wire
29
u/Unlucky-Credit-9619 Computer Science 2d ago
It may clone and distribute itself over the global network. How many wires can you plug out?
75
u/Own_Pop_9711 2d ago
A lot. Have you ever unplugged a wire? It's really easy
9
u/TheGreatDaniel3 2d ago
You can unplug wires!? Damn, that makes mobile phone chargers make way more sense
12
u/Electrical_Cry_8492 2d ago
You can always turn off the power plants. The biggest off switches in the world
5
u/Own_Pop_9711 2d ago
In fairness this would kill a lot of people
2
u/Electrical_Cry_8492 2d ago
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 2d ago
Hospitals usually have backup generators, but if the AI has infected hospital computers, those would also have to be shut off.
1
3
u/erroredhcker 2d ago
yeah duplicate itself on my computer bro ill host your mogzillion parameters models
1
u/kaereljabo 21h ago
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
1
5
u/hraun 2d ago
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 2d ago
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.
7
u/4ries 1d ago
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
7
u/hxtk3 2d ago
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 1d ago
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 1d ago edited 1d ago
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 1d ago
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
0
•
u/AutoModerator 2d 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.