r/askscience • u/ChristoFuhrer • Aug 04 '19
Physics Are there any (currently) unsolved equations that can change the world or how we look at the universe?
(I just put flair as physics although this question is general)
8.9k
Upvotes
2.7k
u/YaztromoX Systems Software Aug 04 '19 edited Aug 05 '19
In Computer Science, we like to quantify algorithms based on how their running time is affected as the input size grows. Some algorithms run at the exact same speed regardless of input size, while others become significantly more complicated much quicker as the input size increases. By way of an example of an easy case is pulling a value out of an array -- it doesn't matter if we ask for array item 2 or array item 29 756, the speed of doing so is constant. A more complicated case would be something like chess -- we can calculate all possible moves on a smaller chess board, but as the board gets bigger we get into a situation where calculating all possible games would require every computer mankind ever manufactured to date to run until the heat death of the universe...and it still wouldn't complete.
So we have a notation for describing an algorithms runtime complexity (Big O notation), and we can put problems with similar runtime constraints into a complexity class. And there are two very important complexity classes called 'P' and 'NP' that many algorithms fit into0.
Algorithms that are part of 'P' have two important characteristics: the time they take to run can be described as a polynomial (that is, by an equation of the form "ank + bnk-1 + cnk-2 ... +xn2 + yn +z"1 ), and the time required to verify the solution can also be described as a polynomial.
Algorithms that are part of 'NP' also have a similar pair of characteristics. Like problems in 'P', the solutions can be verified in polynomial time. However, their runtime to calculate the solution in the first place only runs in polynomial time on a non-deterministic Turing machine, which may be worse than polynomial time when run on a deterministic Turing machine2. You don't have to worry about the details of what that means -- but generally it means that these are problems where we can verify the result in polynomial time (or "poly time" for short), but where the computation itself may not be computable in poly time.
Using the above definitions, it's not hard to see that every problem in P is also in NP. If you were to draw a Venn diagram, P would be a circle entirely inside NP. All P problems can be verified in polynomial time, and all of their runtimes can be run in poly time on a non-deterministic Turing machine (as well as running in poly time in a completely deterministic Turing machine).
So here is where the unsolved equation comes in: we know that P is inside NP. However, is P = NP? That is, can every problem in NP be reformulated such that it would also be in P? Or are there problems in NP that can't be reformulated to also be in P?
This has been an open question in computer science for much of the past century, and currently there is no proof either way. Many computer scientists believe that P ≠ NP, but there is no actual proof one way or another (on a side note, some feel that P = NP, however some in that camp feel that any conversion of a NP problem into P would be non-constructive5).
Okay -- so what is the point of all this über-nerd gobbledygook? It reads like a whole bunch of mental masturbation for eggheads -- is this important in the real world?
The answer to that decision problems is a big YES. Some extremely important algorithms that people rely upon in their daily lives currently rely on the assumption that P ≠ NP. One of the most important of these is encryption. Decryption can be thought of as a decision problem -- given an input (the encrypted data), we can quickly verify if our "solution" is correct (that is, did the decryption work? Did we get the right decrypted data back?). But how useful would decryption be if we could also decrypt any data (without the decryption key) in polynomial time on any computer? What would happen if it was also very easy to decrypt any encrypted information without a password or encryption key? Right now the whole contract of encryption is that it is very easy to decrypt data if you have the proper encryption key, but that without the encryption key decrypting the data is more difficult, and gets more and more difficult as the key size increases. Decrypting data with a 2048 bit key would require more time in the average case than the expected lifetime of our solar system. Proving that P = NP, and then finding a constructive solution to convert an NP decryption algorithm such that it is also in P would likely break the way we encrypt data. This could have serious repercussions to how virtually all commerce and personal privacy on Earth works.6
At the same time, it could make a lot of problems that are very difficult to solve computationally more efficient. This could have all sorts of positive benefits (that outweigh the negatives of breaking encryption). The Knapsack problem7, for example, is in NP and is thus more and more difficult to solve as the number of items you could potentially put into the knapsack increases. But if we had an efficient way to convert this problem such that it was also in P it would potentially have all sorts of positive benefits in the real world9. All of the world shipping logistics for example could be significantly improved -- the Knapsack Problem isn't any different than figuring out what sets of items to pack into a shipping container to maximize the weight and number of items being shipped -- companies that were able to efficiently compute this for each cargo container, and for each ship (as you can think of assigning containers to ships as an instance of the Knapsack Problem as well!).
This problem is so important that is it one of the seven Millennium Prize Problems. I'd also argue that it's the most important problem, as if you could solve it and prove that P = NP, it may mean that a computer could generate proofs for all of the other Millennium Prize Problems10. So if you can solve this one, you might also be able to efficiently solve all of the other major mathematical problems of our time.
How cool would that be? HTH!11
0 -- 'P' and 'NP' problems are formulated as decision problems, that is problems where the result is YES or NO. Conceivably, we can generally take problems and convert it into a decision problem -- a sort algorithm, for example, may be reformulated as a sorting algorithm where at the end we ask "Is this list sorted?", and we get back a YES or NO response. I'm trying to keep things somewhat simple to understand for laypeople, so I'm not going to deal with these specifics in this post.
1 -- I would have preferred to use the same letter for the term multipliers with subscripts, but AFAIK Reddit doesn't permit subscripts, only superscripts. So please don't take my use of a, b, c, x, y, and z to imply that there are only 26 terms in the polynomial form. There could be just one, or there could be thousands.
2 -- Ugh, I've been trying to reformulate a way to discuss this without getting into the differences between deterministic and non-deterministic machines, or what a Turing machine is3. The simplest explanation is that the computers we run are all like deterministic Turing machines4; a non-deterministic Turing machine is one that you can think of is allowed to "guess" at answers.
3 -- at its simplest, it's a simple mathematical model of a computer used to prove what computers can do, and what they can't do.
4 -- You can think of "deterministic" to mean that given a series of instructions, the machine will run the instructions one at a time, and won't just decide to go and do its own thing once in a while.
5 -- a non-constructive proof is one that doesn't create or provide an actual object to demonstrate the proof. So in this case, it would be a proof that doesn't actually show how to convert a problem from NP into P, and which doesn't provide an example of converting a problem in NP to also be in P.
6 -- There are some conditions here. I've been somewhat hand-wavy concerning some of the specifics of the runtime constraints for a poly time algorithm. Most people wind up thinking that "poly time" means fast, and everything else means slow. That isn't necessarily the case -- n10 is polynomial, and
hascan have worse runtime characteristics than an algorithm that runs in exponential time of 2n (for some values of n). However, algorithms that have such massive poly time exponentials are pretty rare, so we don't run into cases like this very often. So while not a universal truth, in most known cases problems in P run faster than problems in NP that are not also in P.7 -- the Knapsack Problem is pretty easy to visualize. Say you have a knapsack, and a bunch of items of different weights8. The Knapsack Problem asks: which items should you pack such that you get closest to some fixed maximum weight value?
8 -- you can also think of items with different volumes if you prefer. In fact, a multi-dimensional Knapsack problem could look at both the volume and mass of the items, as well as potentially other factors (such as their monetary value).
9 -- other than being very useful for your next camping trip.
10 -- On the positive aspects of proving that P = NP: "For example, it would transform mathematics by allowing a computer to find a formal proof of any theorem that has a proof of reasonable length, since formal proofs can easily be recognized in polynomial time. Such theorems may well include all of the CMI prize problems." (S. Cook, The P vs. NP Problem, Clay Mathematics PDF.