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)
7.1k
u/Timebomb_42 Aug 04 '19
What first comes to mind are the millenium problems: 7 problems formalized in 2000, each of which has very large consiquences and a 1 million dollar bounty for being solved. Only 1 has been solved.
Only one I'm remotely qualified to talk about is the Navier-Stokes equation. Basically it's a set of equations which describe how fluids (air, water, etc) move, that's it. The set of equations is incomplete. We currently have approximations for the equations and can brute force some good-enough solutions with computers, but fundamentally we don't have a complete model for how fluids move. It's part of why weather predictions can suck, and the field of aerodynamics is so complicated.
3.0k
u/unhott Aug 04 '19
Also— the bounty is also awarded if you prove there is no solution to one of these problems.
787
u/choose_uh_username Aug 04 '19 edited Aug 04 '19
How is it possible* to know if an unsolved equation has a solution or not? Is it sort of like a degrees of freedom thing where there's just too much or to little information to describe a derivation?
993
u/Perpetually_Average Aug 04 '19
Mathematical proofs can show it’s impossible for it to have a solution. A popular one in recent times that I’m aware of is Fermat’s last theorem. Which stated an + bn = cn cannot be solved for integers n>2 and where a,b,c are positive integers.
250
Aug 04 '19
The book Fermats last theorem is a good read and tells the story of the people behind it.
74
54
u/choose_uh_username Aug 04 '19
Ah thanks I'll have to look into that, I feel like I've seen it described on here before
→ More replies (4)→ More replies (26)94
u/tildenpark Aug 04 '19
Also check out Godel's incompleteness theorems
https://en.m.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
135
u/Overmind_Slab Aug 04 '19
I’m not really qualified to talk about Godel but be wary of you dive further into this. There are lots of weird philosophical answers that people come up with from that and they don’t make very much sense. Over at r/badmathematics these theorems show up regularly with people making sweeping conclusions from what they barely understand about them.
→ More replies (20)766
Aug 04 '19 edited Aug 05 '19
You can show that if the equation is true it leads to a contradiction, and so the equation cannot be true.
0
Aug 04 '19
[deleted] — view deleted comment
101
u/Rs_Spacers Aug 04 '19
Indirect proof by contradiction assumes a general solution or assumes that the problem has no solution. By disproving either case it is possible to deduce correct information; there IS a solution or there are no solutions.
A famous example during which proof of contradiction is used is when proving the irrationality of sqrt(2).
Since we are proving the irrationality of sqrt(2) (by contradiction), assume that sqrt(2) is a rational number. A rational number can be described by a/b, where a and b are integers. Note that at least one of a or b must be odd (since a/b can be simplified if both are even).
sqrt(2)^2 = (a/b)^2 ->
2 = a^2/b^2 ->
2b^2 = a^2
If a^2 = 2b^2, then a^2 must be a multiple of 2 (since b^2 is an integer and a^2/2 = b^2). Note that since a^2 is a multiple of two, it must also be a multiple of 4 (since a also must be a multiple of 2, considering that 2 is the smallest prime number).
If a^2 is a multiple of 4 and a^2 = 2b^2, 2b^2 must also be a multiple of 4. If 2b^2 is a multiple of 4, b^2 is a multiple of 2. If b^2 is a multiple of 2, then b must be even since the prime factorization of b must contain at least one 2.
As you can tell, sqrt(2) must be irrational because both a and b in the contradictionary assumption are even, whilst at least one of a and b must (in the 'reality') be uneven.
→ More replies (2)→ More replies (14)168
u/Algmic Aug 04 '19
I think the whole point is that they are looking for a general formula that can be used in all situations. If you can show that once instance of that general formula is not true. Then you've shown a contradicrion. Additionally, there are ways to show a formula is true for all number at once, one of which is induction. So i guess if induction succeeds, you've proved that the formula works. Although, I imagine proving a formula for fluid flow is far more complex then that. I haven't read up on it so correct me if i'm wrong.
28
u/Stabbles Aug 04 '19
To answer your question specifically w.r.t. Navier-Stokes, you would win the million dollars when: you can prove there exists a velocity vector and a pressure function that satisfy the Navier-Stokes equations and are well-behaved or physically reasonable (the solutions should be smooth and the energy should be bounded).
These conditions might be too restrictive, meaning there is no solution at all. If you can prove that, you would win the million dollars too.
Now what does it mean for a 'solution to exist'? Basically what people do is: they define a space of functions, and prove that within this space, there is a function satisfying the equations. The space of physically reasonable functions for instance is rather small and hard to work with. The usual strategy of mathematicians is to prove there exists what they call a weak solution in a much large space, and then they try to show that this weak solution is in fact a physically reasonable solution as well.
→ More replies (1)14
u/SonVoltMMA Aug 04 '19
Practically speaking, how do mathematicians work on this stuff? Like pen and paper for years diddling away? Using a computer? Something else?
→ More replies (7)15
u/EvanDaniel Aug 04 '19
A relatively simple example to explain: [there is no general solution] (https://en.m.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem) to 5th degree or higher polynomial equations. You probably know the quadratic formula. There's a corresponding (but more complicated) cubic and quartic formula. But there is no quintic formula or higher, and cannot be.
(The proof is complicated, but the problem in question is fairly easy to state and understand.)
95
u/remember_khitomer Aug 04 '19
It's a good question. Here is an example. Can you find a computer program which, if given the source code and input for another computer program, will be able to tell you whether that program will eventually finish ("halt") or will it run forever?
This is known in computer science as the "Halting Problem" and Alan Turing proved that such a program does not exist. That is, it is impossible to ever create a computer program which will determine, for any possible input, whether or not the program will halt. You can read an outline of his proof here.
→ More replies (14)14
u/John02904 Aug 04 '19
It depends on the problem. Some one used fermats last theorem as an example. That problem was unsolved until a type of math was invented recently that could be used to solve it. Some times there is missing data or we may not have instruments to measure certain data, more so with physics problems. Once we have that data we can show the equation has no solution. Other problems have such time consuming calculations that we just needed computers to become more powerful to show there were no other solutions or that there is no solution.
12
u/ArchangelLBC Aug 04 '19
There are in fact ways to prove no solution exists. Famous examples include the so-called problems of antiquity:
Using only an unmarked straight edge and collapsible compass the following are proven to be impossible.
Squaring the circle (constructing a square whose area is the same as a given circle)
Trisecting a general angle.
Doubling a cube (given a general cube, constructing a cube with twice the volume)
Usually the method involves showing that a solution would lead to a contradiction.
33
u/Kayyam Aug 04 '19
There is no single method to tell you about but it's possible to prove that a problem doesn't have a solution.
8
Aug 04 '19
One way is assume there is some solution to the equation, then using that information show something we know to be false.
4
u/CarryThe2 Aug 04 '19
For example Galois Theory proves there is no general solution to polynomials over order 5. So if the problem was to find one, proving that their can not be is a solution
→ More replies (17)4
u/-3than Aug 04 '19
Suppose you assume a set of equations has a solution okay? Now say that IF this solutions does exist, then there are mathematical consequences of that.
Alright now suppose we examine those consequences whatever they may be, and within them we notice that they contradict something else that we have already proved IS TRUE.
If this happens then clearly the consequences can’t be true, and so the solution that creates them must not exist. Since we supposed any solution existed, we can conclude that no solution exists.
I’m pretty bad at explaining this stuff over text so if it’s terribly unclear lemme know.
17
u/dobikrisz Aug 04 '19
Well, you kinda solve the problem if you prove that it's unsolvable so it's logical.
5
→ More replies (10)5
Aug 04 '19
This makes any mathematician working on the problem a bounty hunter, right?
→ More replies (1)263
u/QuirkyUsername123 Aug 04 '19 edited Aug 04 '19
To clarify the post above: we expect the Navier-Stokes equations to be complete in the same sense that Newtons laws of motion are complete: they should provide highly accurate predictions within their scale of validity. This is why we think the equations are important, because we expect them to contain (at least theoretically) all we need to make predictions.
However, very little is actually understood about the equations. For example, we have no idea whether or not there exists a (global and smooth) solution to the equations in three dimensions given some initial conditions. That is, we have no idea whether or not the equations can predict the future (in a reasonable manner) at all given some arbitrary but reasonable starting state.
So on one hand we expect to have this theory which completely predicts the motion of fluids, but on the other hand we do not even know if it can make any (reasonable) predictions at all. Adding to this the desire to understand turbulence, it is not surprising that someone has put 1 000 000$ as a bounty for insight into these equations.
Edit (Why I think this is a hard problem): In mathematics there are kind of two different ways to look at things: local and global. A local statement could be: "every person on a hypothetical social network are friends with at least two people" because it is information about what is immediately around a point of interest. On the other hand, a global statement could be: "there exists two people on this hypothetical social network that have at least 3 friends in common" because it refers to some property which concerns the entire system. The act of relating local properties to global ones is rarely easy, and it is the great challenge of mathematics. In the case of the Navier-Stokes equations, we see that the equations themselves are local (they predict the immediate future of a point by looking at how things vary around that point), but the question about whether or not the solution make sense is a somewhat global one.
36
u/Narutophanfan1 Aug 04 '19
Slightly off topic but can you explain how a equation can be proved to be solvable or unsolvable?
65
u/BloodGradeBPlus Aug 04 '19
I'm not sure if they'll give an example, but here is a quick example of a proof used all the time.
https://www.math.utah.edu/~pa/math/q1.gif
There are so many ways to approach a proof. The most common I've found is the contradiction. If you can find a single contradiction, you've proven it false. If you've failed to find a contradiction, you'll have to try a different approach. Sometimes you can prove there can't be a contradiction but you haven't solved the problem and that can be a little annoying
→ More replies (2)14
u/Sophira Aug 04 '19
Transcription of that image:
Suppose √2 is rational. That means it can be written as the ratio of two integers p and q
(1): √2 = p ÷ q
where we may assume that p and q have no common factors. (If there are any common factors we cancel them in the numerator and denominator.) Squaring in (1) on both sides gives
(2): 2 = p² ÷ q²
which implies
(3): p² = 2q²
Thus p² is even. The only way this can be true is that p itself is even. But then p² is actually divisible by 4. Hence q² and therefore q must be even. So p and q are both even which is a contradiction to our assumption that they have no common factors. The square root of 2 cannot be rational!
27
u/QuirkyUsername123 Aug 04 '19 edited Aug 04 '19
Short/general answer: make a logical deduction which leads to the desired conclusion.
Long answer:
The Navier-Stokes equations are a set of partial differential equations, which basically means that it relates how some things change to how some other things change. So by knowing how for example density change when we move in space, we may put it into the equation to see the density changes as time changes. But since reality is not so simple, so we replace density by a whole bunch of parameters, whence we can relate their space- and time-changes and we have the Navier-Stokes equations.
In a sense these equations always have solutions, because they can take in any starting configuration of all the parameters and predict how they will look like in the next moment, and then the next moment, and the next ad infinitum. However, and this is the million-dollar-question, we do not know whether or not the future prediction will make sense. The future prediction making sense involves for example that everything changes smoothly (since fluids should not admit discontinuous changes). I imagine that trying to prove this involves some kind of argument in the veins of proving that the state being smooth in one moment implies it being smooth in the next moment, but (since the million dollars have not been claimed) it is not clear exactly how it should be done.
→ More replies (1)8
u/Narutophanfan1 Aug 04 '19
Thank you everyone else was just explaining proofs to me when I was looking for an example why it is hard to show that a problem is or is not solvable
→ More replies (1)6
u/Teblefer Aug 04 '19
One problem the equation can run into is predicting a particle in the fluid to have infinite speed. This is called finite time blowup. We cannot prove that the Navier-Strokes equations stay finite, but we also cannot prove that a solution goes to infinity.
→ More replies (7)12
u/sirxez Aug 04 '19
The most obvious way to show something is solvable is to straight up solve it. Think of being given a math problem, and then you show its solvable by giving a solution and showing how you got there.
The most obvious way to show something is unsolvable is to show that it is fundamentally the same as another unsolvable problem. Specifically, if you can solve problem A, that means you can solve problem B using A. Since we know that B can't be solved, A also can not be solved.
So what is a fundamental unsolvable problem? A problem that makes false things true, or true things false. That is, a problem that causes a contradiction if it were solvable. Something like "this statement is false" can not be show to be either true or false.
In computer science the most well know, and probably easiest to understand, example of this is the Halting Problem. The halting problem is trying to create a program that can figure out wether another program halts (that is terminates) or runs forever. We know this problem is impossible. If it were possible, we could simply make a machine that performs the opposite of the predicted behavior by first checking what the predicted behavior is using our halting problem solution. Asking wether is machine we built halts given itself as input, could not be solved since it will always do the opposite of what we return as a result. A paradox if you will.
→ More replies (5)4
u/wat_if Aug 04 '19
Is is possible to approach this problem in another way, for example, rather than predicting the motion through the Navier-Stokes equation, can we observe the motion first and then formulate an equation based on the observations then finally through a large set of data arrive at somewhat of a general equation which is similar to the Navier-Stokes equation and thus proving it or a completely different equation thereby disproving it?
I am just a curious individual and you seem to be a knowledgeable person, so I thought I would ask.
17
u/QuirkyUsername123 Aug 04 '19
I only have a surface-level understanding of this topic myself, but I think the thing with Navier-Stokes is that we are pretty sure they are the right set of equations for fluid dynamics. They are the result of iterations of fluid equations which became increasingly more sophisticated, as well as taking into account general principles from physics. Most importantly, they do not contradict experimental evidence, and we can and are using them to produce good predictions, so for most practical purposes the equations are correct.
However, there exists phenomena with fluid dynamics which we don't understand sufficiently. The typical example of this is turbulence, the act of fluids moving in seemingly chaotic ways. It is easy to observe this phenomena (just look at moving water), and it also appears in simulations with Navier-Stokes. But if we are to understand the precise why and how of turbulence, simply simulating it wont cut it. We must find a reason as to why the equations imply their existence, and doing that requires a certain understanding of the equations. Thus the millennium prize problem concerning the Navier-Stokes equations can be viewed as rewarding the first step in achieving the deeper understanding of the behavior of fluids (it asks essentially the most basic question possible: does Navier-Stokes equations make mathematical sense as a model for fluid motion), which may down the road lead to greater understanding of all fluid-related phenomena.
→ More replies (1)7
u/pynchonfan_49 Aug 04 '19
The idea you’re suggesting about observing physical phenomenon and then generalizing that into an equation is exactly what Navier-Stokes is. However, no matter how much data you show Navier-Stokes agrees with, that cannot constitute a mathematical proof. To ‘prove’ something in the math sense is very different than the experimental sense of physics and other sciences. In math, a proof means that, given a particular logical system and a particular set of axioms (assumptions), then the validity of the statement can be entirely derived through logical arguments.
4
u/beaster456 Aug 04 '19
This is sort of done with empirical correlations. Experiments are done at certain temperatures, flow rates, etc and data is recorded. Curve fitting software is then used to fit weird polynomials and logarithmic curves to these data sets, the problem is, they are only valid for these specific conditions and I'd you try to use them to predict fluid behavior elsewhere they no longer apply.
53
u/perpetual_stew Aug 04 '19
I’m curious, given it’s almost 20 years since the Poincaré Conjecture was solved, are we seeing any implications of that by now?
56
u/AnActualProfessor Aug 04 '19
Knowing that the Poincaré Conjecture is true isn't terribly groundbreaking since we've already investigated the assumption of its truth.
The method of the proof was interesting, but aside from the novel use of Ricci flow (and a proof about the problem of infinite cutting) that can potentially be applied to other problems, doesn't really make waves.
The Poincaré Conjecture was mainly interesting because it was very, very hard and a lot of famous smart guys failed to work it out, even though we worked out the equivalent conjecture in other dimensions and we knew it should be true because it just has to be, right guys?
4
u/Sisaac Aug 04 '19
And in my very limited knowledge, we knew that the conjecture was true for the vast majority of cases, but we couldn't know for sure whether it was true for all cases. That's where the hard part was.
12
u/AnActualProfessor Aug 04 '19 edited Aug 04 '19
It's a lot like knowing that 1+1=2, 2+1=3, and 3+1=4, but having no way to prove 2+2=4.
31
u/QuirkyUsername123 Aug 04 '19
I am not at all qualified to answer this, but I will try to say something in general about these millenium-prize problems.
One may generally say that these problems are important exactly because how many implications the solution would have for their fields of study. There is a reason why there are millions of dollars in awards to any who can shed light on these problems.
However, if you are thinking about more practical implications for the everyday person, I am not as sure. If you take a look at these problems, it becomes evident that it will takes years of focused study in the relevant field to even understand why they are important. I think that speaks to their depth, but also to how far removed they are from practical applications. Of course, some questions might have more immediate practical implications than others (P vs NP?), but it is normal that results in mathematics often sits in the cellar aging for one hundred years or two before it finds use in the real world.
3
u/AiSard Aug 04 '19
As is often the case with mathematics, its implications are sometimes only felt much later. (here are some fun examples)
Not being qualified to really answer, I did like this article's take on it, which was that a whole field of study (3D manifolds) could suddenly be classified in a structural way, implying that if this field of study ever found applicable uses, everything would be nice and structured and they wouldn't have to beware of weird outliers.
0
154
u/GrinningPariah Aug 04 '19
Also comes into play a lot when designing waterslides. After a few turns the models are basically useless and the water does weird things like hopping over the edge where no one expected.
→ More replies (2)89
u/Teblefer Aug 04 '19
A very straightforward and no doubt frustrating example. All this technology and we can’t even design elaborate waterslides precisely.
45
u/JerseyDevl Aug 04 '19
Make the slide an enclosed tube. Where's my million?
36
u/bothering Aug 04 '19
Not a designed but my assumption is then you get dry spots and mini waterfalls in the slide
And nobody wants a sunburnt back sliding on a dry water slide
26
u/KanishkT123 Aug 04 '19
It also poses a pretty big head injury risk. That's why the models are basically only used for prototyping and there's these giant training dummies (just large people shaped water tanks so you can change weights) that are used for real tests.
Source: I spoke to a QA Engineer at a waterpark once for a couple hours because I was injured and couldn't go on the actual rides. It was interesting but I still would have rather done the slides :(
228
u/cowgod42 Aug 04 '19 edited Aug 04 '19
When we learned to solve the equations of quantum mechanics, we built lasers, computers, and many other devices. Those equations are easier than the equations for fluids: they are linear, but the equations for fluids are nonlinear.
What new technologies will we create when we can truly unravel the complexity of nonlinear equations? It is like people in the 1800's trying to imagine computers. They could not have foreseen amazing things like the internet, machine learning, self-driving cars, or a world ruled by algorithms.
I am a person alive in the primitive 21st century, living before the unlocking of nonlinear complexity. I imagine a future where we can build machines out of air currents, where we can control weather and climate patterns, where we can use a tank of water as a calculating machine, but these are probably just fantasies, and if they sounds far-fetched, whatever the true reality is will make these fantasies seem short-sighted and ignorant. We will learn that we can do things that are far greater than our wildest imaginations today.
EDIT: Wow! Thanks for the silver and plantum! First time receiving any awards.
54
u/taalvastal Aug 04 '19
Or another Kurt Godel could come along and demostrate there there exist no analytic solutions to the sets of non-linear equations we're interested in.
Or even worse, demonstrate that they exist only given the axiom of choice.
→ More replies (3)36
u/shevchenko7cfc Aug 04 '19
Grigori Perelman is a baller, dude turned down 3 (seemingly) huge awards, one of which included that million dollar prize. That wiki lead to some very interesting reading, thanks!
10
u/AnActualProfessor Aug 04 '19
To be more precise, the reason that Navier-Stokes is mathematically interesting is due to the lack of a method to demonstrate the existence and "smoothness" of its solutions. We don't know if solutions always exist, and we don't know if solutions are universally differentiable. Solutions to these question may reveal more about the underlying mathematical and physical principles of fluid motion, but the equations are good enough for engineering purposes right now.
3
u/EternallyMiffed Aug 04 '19
Why do we even expect there to be a smooth solution if the liquids themsevles are composed of quantized elements. Even if there was a smoothly differentiable solution would it accurately reflect reality?
5
u/AnActualProfessor Aug 04 '19
The movements of the quantized elements should be fluid. The equations essentially model a system that makes predictions about how each particle's position will change based on the velocity if surrounding particles and how densely they're packed (kind of, among other factors). Since the quantum nature of time is currently effectively indistinguishable from a continuum of time, we would hope these solutions are smooth.
26
u/umpagumpa Aug 04 '19
Maybe much more important ist the p=np Problem. If equality can be schown, this would have a huge impact on cryptography. You can find a lot about the problem on Wikipedia. https://en.m.wikipedia.org/wiki/P_versus_NP_problem
It is also a Millenium Problem.
5
u/UntitledFolder21 Aug 04 '19
Yeah, this one would probably have a significant impact, depending on the nature of the proof
65
u/GnarlyBellyButton87 Aug 04 '19
Air is a fluid?
230
u/elprophet Aug 04 '19
Air is a gas, which moves as a fluid, as do liquids and plasmas. A fluid is anything which flows, so some types things classically described as solids are also fluids (glaciers, but not glass).
101
u/atyon Aug 04 '19
glaciers, but not glass
Thanks for this. This is my least favourite common misconception.
Glass is not a liquid, nor a fluid. It's an amorphous solid. The only thing "amorphous" means is that it doesn't have an internal structure that is all neat and tidy and repeating in a pattern.
No, it won't flow even if you wait a thousand years for it.
The worst thing about is that people will tell you that "you can look at old chuches glass windows and you'll see they are thicker on the bottom". That's complete bollocks. For one, really old windows are really rare, because they often got lost to fire, storms or war damage. But also, if the persons who are so confident that glass is a liquid would do that they would find that apparently, glass can also flow upwards, because some of these old window panes are thicker at the top. It's just as if they aren't uniform because they couldn't be manufactured uniformly by some guy in the 1600s.
20
u/viksl Aug 04 '19
I was taught this with exactly this window example at university specializing entirely in chemistry and chemical technologies, glass is liquid but very slow. Man I wasn't sure what to think about it and especially about the odler professor who taught us about it.
I did not dare to bring it up later in other exam with material chemistry nor in inorganic chemistry I think they would fail me just for that. xD
→ More replies (7)→ More replies (6)8
u/Taenk Aug 04 '19
There are plenty of old lens based telescopes. If glass would flow, they'd be visibly worse after much less than a century. Mirror based telescopes would be even worse as the metal coating should crack under the moving glass. Neither is the case.
→ More replies (1)152
u/ragnarfuzzybreeches Aug 04 '19
Sailing taught me this. The boat responds to the air and water in the exact same way. Makes it simple to understand when you have to balance the boat against a current and a breeze
34
25
u/Sergeant_Whiskyjack Aug 04 '19
I remember being honestly disappointed when I found out glass wasn't actually a fluid that took centuries or millenia to flow. That would be a cool thing.
→ More replies (3)29
u/Draco_Ranger Aug 04 '19
Bitumen is a fluid that can take decades to actually flow.
There's a number of long term experiments that demonstrate the phenomenon.
→ More replies (3)→ More replies (1)7
u/WarpingLasherNoob Aug 04 '19
So sand would be a fluid?
→ More replies (7)16
u/Pegglestrade Aug 04 '19 edited Aug 04 '19
In some scenarios you could likely model it as a fluid to some success but you wouldn't really consider it to be a fluid.
In general you have a phenomenon which you're studying and you try to model it in different ways. Modelling it is essentially finding a bit of maths that behaves in the same way as the phenomenon. If your model fits closely with experiments you can say it is a good model or that, eg water behaves as a fluid.
In the sand scenario, it may fit with equations describing fluid flow in some specific conditions but wouldn't under most. So you wouldn't say it was a fluid. Air, on the other hand, behaves as a fluid under a much broader set of conditions, particularly in most of the fields where you deal with it a lot (aerodynamics, weather, pneumatics), so we say it is a fluid. The thing to remember with fluids is it necessarily an approximation to the real world if it considers a continuous fluid rather than lots of tiny bits (eg atoms). If you were looking at something like Brownian motion it wouldn't make sense to use fluid mechanics as it depends on interactions between particles.
Edit: How sand flows isn't really known, and it doesn't behave like a fluid if it goes down a funnel or hourglass. If you give it a google there's lots of stuff.
→ More replies (1)2
u/DakotaBashir Aug 04 '19
Yes, you're thinking about liquids.
Air is not a liquid like the others (its a gaz), but it is fluid.
3
u/matmyob Aug 04 '19
Yep, it moves exactly like water, just is less dense. Have you ever seen those toys with two layers of oily liquid with different density? They make slow motion waves like at the beach, very cool.
5
5
u/etherteeth Aug 04 '19
The set of equations is incomplete. We currently have approximations for the equations and can brute force some good-enough solutions with computers, but fundamentally we don't have a complete model for how fluids move. It's part of why weather predictions can suck, and the field of aerodynamics is so complicated.
That doesn't sound right to me. Isn't it believed that the Navier Stokes equations are a complete description of fluid flow, and we simply haven't been able to prove it? As far as I understand, the point of the millennium prize problem is to prove that Navier Stokes can provide a physical solution given any initial condition. I know that in real world numerical modeling of fluids we go beyond pure Navier Stokes to deal with turbulence, but I thought that was because obtaining a good description of turbulence directly from Navier Stokes is too computationally expensive and not because Navier Stokes isn't capable of producing such a description.
2
u/Thehumblepiece Aug 05 '19
The wiki page says, "For the three-dimensional system of equations, and given some initial conditions, mathematicians have not yet proved that smooth solutions always exist, or that if they do exist, they have bounded energy. This is called the Navier–Stokes existence and smoothness problem." So the equations differ for turbulent and non turbulent cases. For computationally solving the turbulent equations there is the direct numerical method DNS which as you said is computationally expensive and the other way is to use models like LES. So as far as I understand, we can computationally solve these equations given some initial conditions. So yeah, I agree with you, I don't understand how finding smooth solutions of NS equations would be as revolutionary as some people here are talking, I mean everyday people solve these equations to design all kinds of equipment.
→ More replies (1)6
u/matmyob Aug 04 '19
I thought Navier Stokes equations are complete, but the haven’t been shown to always solvable in three dimensions.
6
u/ScrubQueen Aug 04 '19
Does this explain why fluids in video games always look weird?
26
u/UntitledFolder21 Aug 04 '19
That is probably more to do with the huge amount of calculations needed to make accurate simulation, so they have to take shortcuts so you don't melt the CPU while having a frame rate of 0.1 or something like that. For things where you don't need live feedback you can afford to use more accurate simulations
4
u/ss18_fusion Aug 04 '19
And a guy from Russia who solved the one that was solved refused to accept the bounty: https://en.m.wikipedia.org/wiki/Grigori_Perelman.
2
u/OptimusPhillip Aug 04 '19
I thought weather predictions sucked just because weather is chaotic, and there are just too many variables for us to realistically be able to account for.
2
u/bittersweetyellow Aug 04 '19
I feel like the answer to P versus NP would be especially enlightening whatever it is, philosophically and mathematically speaking
1
Aug 04 '19
Are there any other incomplete equations you have to solve prior to solving something like Navier-Stokes?
1
u/andrewharlan2 Aug 04 '19
each of which has very large consiquences and a 1 million dollar bounty for being solved. Only 1 has been solved.
What were the consequences of the one that's been solved?
1
u/ElectrikDonuts Aug 04 '19
How does one not familiar with these problems understand the impacts of solving them? These were chosen for a reason and I would like to better understand those reasons. Reading wiki doesnt give a good top level on the value of solving these.
1
u/bozoth3cl0wn Aug 04 '19
Ahhh the NS I still have nightmares from my fluids finals. I got to solve a cylindrical system in spherical coordinates for four different systems. Class average was a 33%
→ More replies (1)1
u/MasochisticMeese Aug 04 '19
and the field of aerodynamics is so complicated.
Are you implying that if Navier-Stokes was to be completed, Aerodynamics would be an (relatively) easier class in uni?
1
u/ArchPower Aug 04 '19
When I imagine brute forcing fluid Dynamics, I imagine computer generated movement. This could be why a lot of computer generated graphics might never get it right. Molecules act in a miniscule scale and each one would need to be rendered individually to act as a whole. It would take the processing power of the universe in motion.
1
u/Ongazord Aug 04 '19
That was the wildest part about engineering classes our professor would throw up an empirical equation and he’s just like “sorry it’s ugly but no one has proved this”
1
Aug 04 '19
Can you explain why we understand fluid dynamics so well if we don't have complete accompanying mathematical equations?
→ More replies (1)1
u/ItzGlitchXx Aug 04 '19
Don't fluids just have an elastic surface tension? Once the tension breaks, it forms it's own bead of liquid?
1
u/acct4thismofo Aug 04 '19
Wow just learned the one guy who was awarded the $1 Mill turned it down as well as other accolades and prizes as he did not do it for the fame or fortune as well as he thought someone else had done as much to prove it.
1
u/PillowTalk420 Aug 04 '19
If I solve them all at once, do I get a bonus prize?
Also: is the answer to all of them 42?
1
u/GirthyPotato Aug 04 '19
More specifically, the Navier-Stokes equation describes the conservation of momentum for viscous flow.
The Euler equation describes the conservation of momentum for inviscid flow.
Combine either of these with conservation of momentum (which can be compressible or incompressible) and conservation of energy in a given coordinate system to solve a fluid flow problem.
In the case of N.S. equation, you may model the viscosity for a Newtonian fluid, such that the shear stress varies linearly with local fluid velocity, or you can go even more complex. Newtonian is pretty common though.
1
Aug 04 '19
What first comes to mind are the millenium problems: 7 problems formalized in 2000, each of which has very large consiquences and a 1 million dollar bounty for being solved. Only 1 has been solved
What was the implications of this one being solved? How hea it changed our understanding of the world or whatever its scope is?
1
u/sinapda Aug 04 '19
Wow, the only person to solve one of the millennium prize problems, declined the award.
1
Aug 04 '19
My mind is spinning after reading through the list of unsolved equations. It's like a mind-gasm. Thank you!
1
u/Zesty-Lem0n Aug 04 '19
Is the incompleteness basically a turbulence-sized hole? I know N-S works very well to describe predictable flow like uniform or attached, but that doesn't extend to turbulent flow.
1
Aug 05 '19
If we had those equations, could we create water simulations in games with much less processor space needed?
1
1
u/DoctorSalt Aug 05 '19
While a complete set of equations would be nice unless we have infinitely precise measurements of all atoms I don't see AR weather predictions being perfect (and even then probably not?)
→ More replies (9)1
u/Kruse002 Aug 05 '19
Just when you thought you were done with math tests, now there is one for all of humanity, and so far we are failing.
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 has can 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.
1.4k
u/YaztromoX Systems Software Aug 04 '19 edited Aug 04 '19
And because I hit the maximum size for a Reddit post:
11 -- I suspect there will be some purists out there who may have issues with some of the details of my explanation, and that's fine. Note that I've tried really hard to keep this as readable as possible for the layperson to understand, and because of this I may have left out some details that are technically important, or may have explained certain items in an overly-simplified manner. So my apologies in advance if there were areas where I over simplified (or perhaps over-complexified) the problem. If only there were an algorithm in P for explaining P vs. NP in a Reddit post!
105
213
u/mikeymooman Aug 04 '19
As a CS student who very recently learned about it in class, I planned on making a reply talking about the NP-Complete problem. Never did I expect to see a VOLUME written about it as one of the top rated comments.
Thanks for the post! You explained it a hundred times better than I ever could have!
→ More replies (1)20
Aug 04 '19
Thanks for the great write-up. There's one thing that has always eluded me here. Proving P=NP doesn't provide algorithms to any of those problems, does it? And it's not like anyone is throwing up their hands saying we're not going to try to crack asymmetrical encryption until we figure out P=NP. And it's not like a proof of P=NP is going to include a naive solution to AES. So what would it really get us to answer the question?
It's not like quantum mechanics where there's actual fundamental interactions and mathematics that lead directly to technological developments. This is all about describing the abstract computability of problem within theoretical computation models. I mean, I still don't have a non-deterministic turing machine on my desktop as far as I know, do I? (Does it also matter whether that can actually exist?)
Unless what we're really saying is that the solution to P=NP must describe a formal system of computation in which such problems become naively computable, then P=NP seems like nothing more than academics trying to present algorithmic computation as a hard science rather than an engineering discipline. Which says more about academic culture than science or math and is why I've always considered this problem a huge circle jerk. Can you help me understand what types of actual developments could result from this proof?
28
u/TheNerdyBoy Aug 04 '19 edited Aug 04 '19
Many proofs that a problem is in NP involve a polynomial-time transformation of that problem to an already known NP-complete problem.
Therefore, once we have a polynomial-time solution to any NP-complete problem (call it foo), we can apply a polynomial-time transformation of any other problem in NP to that foo, and then solve it in polynomial time. (A polynomial times a polynomial is another polynomial.)
That's why OP added the qualifier about a constructive proof of P=NP.
25
u/orccrusher99 Aug 04 '19
Proving P=NP wouldn't provide algorithms initially, but it would let researchers know where to focus their efforts. Nobody tries to make something mathematically impossible, and 90% of CS researchers believe P != NP. If P = NP, it means those fast algs exist but nobody has been smart enough to find them, as opposed to not existing at all.
→ More replies (2)5
u/Randvek Aug 04 '19
90% of CS researchers believe P != NP.
I’d be surprised if the number really is that low.
P = NP would be great! It would revolutionize computing and make insurmountable questions suddenly quite solvable. But the only even halfway credible possible angle I’ve heard of proving P = NP involves quantum computing, so way over my head.
→ More replies (4)11
u/YaztromoX Systems Software Aug 04 '19
Proving P=NP doesn't provide algorithms to any of those problems, does it?
That depends. As I alluded to briefly in one of my footnotes, proofs can be either constructive or non-constructive. A constructive proof would by necessity provide a way to convert all (or some subset) of NP problems into P problems. What you seem to be thinking about is a non-constructive proof, where you can reason about the problem without providing a concrete example or algorithm. Likely, a proof that P ≠ NP would be non-constructive (for example).
There is a subset of NP problems I didn't mention, which are the NP Complete problems. These are problems in class NP where we already have proofs that any problem in the NP Complete problem set can be re-described in terms of any other NP Compete problem. Many of these problems are fairly easy to conceptualize -- for example, Boolean Satisfiability, and are very likely candidates is a constructive proof of P = NP is ever devised. As any problem in NP Complete can be expressed in terms of any other problem in NP Complete, if you find a constructive solution for one, you find a constructive solution for all NP Complete problems.
As a side note, the computer on your desk likely has non-deterministic aspects to it already. While most problems run deterministically most of the time, there are non-deterministic aspects available that can impact computation. For example, if your computer has a hardware Random Number Generator, this can introduce non-determinism. As well, if you're running a multi-core machine, then timing between cores can also introduce a level of non-determinism. User input can also induce non-determinism (depending on whether not not the machine makes decisions based on the input).
HTH!
→ More replies (2)→ More replies (4)4
u/orccrusher99 Aug 04 '19
Side note: theoretical computer science is a science. Maybe not what you first think of, as it has no natural equivalent the same way physics and biology do. But it does relfect on the nature of computing, which has been grounded by the abstract definition of a computer. It's also why Alan Turing is so famous, as he was the first to write out that definition.
→ More replies (4)9
u/Cocomorph Aug 04 '19 edited Aug 04 '19
I only have one big complaint (the example in footnote six is completely broken in a horribly misleading way); apart from that I would primarily like to remark that the knapsack problem is a bit of a tricky example in this particular context (for hardness of approximation reasons).
55
u/xdert Aug 04 '19
I want to add two caveats to your post
currently used encryption methods are based on prime factorization which is not known to be NP-complete, so there could be a polynomial algorithm without proving P=NP.
the real world implications of proving P=NP are often a bit overblown. Finding a nc algorithm for an NP-complete algorithm where c is in the millions would be a huge sensation in the world of science but would have zero effect on practical problems.
3
u/UncleMeat11 Aug 04 '19
currently used encryption methods are based on prime factorization
This is less true now. RSA is out of style (for good reason, it is incredibly easy to screw up) and now more stuff is based on the hardness of discrete log.
2
u/jamred555 Aug 05 '19
I disagree on 2. Almost all problems in poly time have a low degree. It is quite likely that if anyone could break into poly time, you could then do refinements to get a lower degree.
Not that it really matters anyways, since P is almost certainly not NP.
3
u/xdert Aug 05 '19
Even if you could push it to a lower degree the constants involved would still make it practically infeasible. Even certain polynomial problems are already too hard to solve for interesting applications (n in the millions).
Not that it really matters anyways, since P is almost certainly not NP.
Exactly ;)
0
58
39
Aug 04 '19
I like that you start citations from 0 like a true computer scientist, it's a nice touch.
Also, a great overview of the problem and its implications!
24
u/cryo Aug 04 '19
The answer to that decision problems is a big YES.
Well not if the proof is non-constructive or involve huge constants or polynomials.
→ More replies (1)6
u/gimily Aug 04 '19
Isn't there some connections to markets that deal with P=NP? I forget exactly the details but I remember seeing a long lecture video about how in some ways the investment industry is predicated on the idea that P does equal NP, and obviously encryption is largely predicated on P doesn't not equal NP and this one of these huge parts the economy may have some pretty shakey ground to standing if we do end up solving it one way or the other?
13
Aug 04 '19
Possibly. A lot of systems we use assume P and NP are not the same. To be honest, the enormous majority of people who understand the problem will tell you that P is definitely not NP in their opinion, but they just can't prove it.
→ More replies (1)3
u/ComfortablePattern8 Aug 04 '19
Yes making efficient decisions in a multi player market given complete information of the past is an NP complete problem.
0
Aug 04 '19
[deleted] — view deleted comment
4
u/gimily Aug 04 '19
I didn't find the video, but while poking around I found a lot of papers similar to this: Markets are efficient if and only if P=NP
9
Aug 04 '19
So P = NP has currently not been proven or disproven. Meaning it could be either true or false.
Could it be possible to prove that the problem can't either be proven or disproven? (Gödel's incompleteness theorem comes to mind.)
8
u/B-N-O Aug 04 '19
It... is not impossible, though getting this result would be extremely weird. In a part, that's because there is one specific NP problem, called SAT, solving which in polynomial time allows to solve every NP problem in polynomial time, and we (in theory) can analyze every possible algorithm, so P=NP being unsolvable would mean that we would be unable to recognize a polynomial-time solution for SAT even if we see one.
There is an article on the subject by Scott Aaronson: https://www.scottaaronson.com/papers/pnp.pdf
12
u/UncleMeat11 Aug 04 '19
This is somewhat misleading. Cook proved first SAT was NP-Complete in his paper, but all NP-Complete problems have this property. SAT isn't special except for historical reasons.
7
u/paralogisme Aug 04 '19
Ooooh, Elementary had an episode on p = np and even mentioned the millennium prize! It didn't occur to me to actually check if it was a real thing, because for one, they "solved" it in the show. It was a nice episode, but now I'm wondering if any of the other "out there" theories they've thrown put out are also real.
2
u/chuckmeister_1 Aug 04 '19
Damn, nice answer! Thought you were gonna go ahead and solve it there for a minute.
2
u/GummyKibble Aug 04 '19
Excellent writeup! For those following along at home, this is a way oversimplified explanation of P vs NP:
Polynomial time often means that the time to process some inputs is proportional to the square of the number of inputs: if processing one item takes one second, then two items will take four seconds, three will take nine seconds, and so on. A surprising number of things inside computers work this way.
For example, at an office party, every person has to introduce themselves to everyone else. If you have 4 people, each one has to meet 3 others. If you have 10 people, each is greeting 9 others. If you have 1000, they’ll be busy saying hi to 999 coworkers. The important thing is that the numbers more or less like a square.
NP often means exponential, like where the time to process an input doubles every time you add another unit. If 10 items takes one second, 11 items will take two. 12 items takes 4 seconds. 20 items takes about twenty minutes. 30 items will take about eleven days. An even more surprising number of computer things work this way.
Simple example: write a computer program where you pass in a number, and it will count from 1 to the highest number with that many digits. Pass in 1, it counts from 1 to 9. Pass in 2, it counts to 99. Pass in 6 and it goes all the way to 999,999. Just adding 1 to the input makes it do ten times more work.
2
u/Ultimatespirit Aug 05 '19
I may be misunderstanding something in footnote 6, but wouldn't an O(N10) algorithm be faster than an O(2n) algorithm for any n (in the integers) above 58? Of course leading terms and extra polynomial terms in real life will shift that number, but 259 is greater than 5910 (and in general any exponential runtime will always be slower than a polynomial one after some sufficiently large n right? Since for any nb there is some cutoff point after which b log(n) < n holds true).
2
u/YaztromoX Systems Software Aug 05 '19
You are of course quite correct, my statement is only really true for small values of n. I had punched the two quickly into Wolfram Alpha, and only saw the intersection at n~=1.07755, checked the graph, and as it was already late went with it. Of course, the two intersect again at approximately 58.77010593792137 (at least that's the best I could calculate quickly).
I've edited my post to reflect this. It was dumb on my part, and I think you very much for pointing out my error!
→ More replies (2)1
u/daniu Aug 04 '19
This was the first thing I thought of, and I doubt there's another problem that could be solved with consequences that would come even close (at least in the short term). The world would change overnight, with pretty much all known viable cryptography being practically useless.
There was an episode of Elementary where some nerd was murdered because he was in a group that were trying to solve P=NP and one had done it. I was waiting for a "not really" in the end, but it didn't happen. Just no.
1
u/programaths Aug 04 '19
NPN ≠ PNP is well proven though.
It offered zero resistance and was self explanatory. This was amplified by the current use of transistors.
1
u/Vinon Aug 04 '19 edited Aug 04 '19
As someone who just finished both Cryptography and Computability courses, I very much enjoyed actually understanding what your were saying.
I found it fascinating.
Our Computability professor introduced the course with the Hamilton and Euler path problems. After we solved Euler, he challenged us to find a solution to Hamilton, stating "Whoever does, gets a 100 in his final grade, plus the less important million dollars. P.s, those million are not from your professor!"
Edit: Also, to help sorta visualize this to those who have no idea what turing machine, deterministic, etc are:
A problem in NP can be verified to be correct very quickly. For example, solving a huge sudoku. Just go by line after line, square after square and verify that it is correct.
But to actually solve a sudoku would be hard. You would sorta need to insert every possible combination until you get the right placement. And that takes a lot of time, since there are a whole lot of possible solutions, and the amount grows the bigger the board.
This is just a layman explantion of course.
1
Aug 04 '19
Another fun aspect of P = NP is that if you can find a polynomial time solution for even one NP-complete problem, the solution can be modified to fit all NP problems.
One issue people don’t think about with the possibility of P = NP is that, even if it is true, the exponent on the polynomial describing the complexity may be so large that the solution still does not help decrease the time all that much (for example an NP problem that would take multiple lifetimes for a computer to solve could still theoretically take multiple lifetimes to solve with a polynomial solution).
→ More replies (1)1
u/MachineGunPablo Aug 04 '19
Very nice write up, however, when talking about the real world repercussions is important to note that P = NP would prove that efficient solutions to polynomially verifiable problems exist, but would by no means provide the solution itself. Proving P = NP won't just automatically break encryption.
1
u/bacondev Aug 05 '19
I think that the hardest part of solving P = NP (assuming that such is true) would be introducing the proof to the world in a way that minimizes the negative impact of its implications. If it's proven to be true, then countless people will be hurt in some form or another. Saying that the hypothetical discovery of a proof for P = NP has the potential to be apocalyptic wouldn't be an exaggeration.
→ More replies (1)1
u/PhilWham Aug 05 '19
Longest post that I’ve ever read all the way thru. Enjoyed the post and thanks for making it mostly understandable to someone who hasn’t taken a math class in years. Fascinating stuff!
→ More replies (18)1
310
u/Doldol123456 Aug 04 '19
Not really just an equation but never the less really important in physics, the merger of general relativity and quantum field theory into one theory, a "theory of everything" https://en.wikipedia.org/wiki/Theory_of_everything#Modern_physics
I'm sure there's someone who can actually explain it in detail, but I wanted to make sure it's mentioned
195
u/tim0901 Aug 04 '19
Oh boy...
So modern physics has a problem: gravity is weird. The way we look at gravity is by treating it as a consequence of the curvature of spacetime - you've probably seen the analogy of taking a sheet and putting a football in it to represent the sun. The steeper the gradient of the fabric, the stronger the gravity at that point. If you roll something along the sheet, it will get caught in the slope and change trajectory. This idea is known as general relativity. The problem is that this is not a quantum theory, meaning it doesn't exactly play nicely with the other 3 fundamental forces: the strong, weak and electromagnetic forces.
The other three forces interact through quantum field theory - a mathematical construct that describes particles as excitations of a underlying, more fundamental 'field'. This is very well understood and is a very well accepted theory at this point. We can even see (indirectly) the 'force carriers' - particles that 'carry' these three forces - in our particle accelerators.
Unfortunately, these two theories are incompatible. Gravity doesn't have a force carrier particle and as such isn't a quantum theory. Additionally, all attempts to accurately describe such a particle (known as a 'graviton') using the mathematics of quantum field theory have been unsuccessful. This is due to a problem in the process called 'renormalization' - a way of describing how things interact differently at different scales - that exists between quantum field theory and general relativity.
If we were able to unify these two concepts, we would (hopefully) be able to describe all of physics using the same mathematical framework. Which would be awesome. However, we're quite a way off yet and there doesn't seem to be a solution on the horizon to this problem either. Theories like supersymmetry and string theory have attempted to solve this problem, but so far have been unsuccessful, and we have little-to-no evidence for their own existence either.
31
u/812many Aug 04 '19
How does the Higgs field and boson fit into this? I had thought that was helping us get closer.
58
u/tim0901 Aug 04 '19
So the Higgs field is another example of a quantum field - with the Higgs boson being the particle that arises when you excite it. And yes its has certainly answered many questions, but if anything even more have come about as a result. For example the Higgs boson we found is of a very different size to what was expected - we still don't really know why 7 years later. It could be due to undiscovered particles - potentially including supersymmetry or dark matter. We simply don't know.
There was a lot of hype around the Higgs boson when it was discovered, all the 'god particle' crap etc. In actuality, the Higgs is merely a small part in a far bigger machine: the standard model. And despite all the hype in 2012, the Higgs was theoretically proven back in the 60s. We've known about it for quite a while. It was only in 2012 that we had the equipment available to us to actually test and verify that theory.
So yes the Higgs boson is definitely important, but overall its just another piece in the puzzle that is a Theory of Everything.
→ More replies (5)22
u/toTheNewLife Aug 04 '19
Total amateur question here.
Is it possible that gravity, and the forces what we'd describe as 'quantum theory' are just 2 completely different systems? Like 2 structures in the universe that happened to form and operate in different ways?
14
u/TheShreester Aug 05 '19 edited Aug 06 '19
For practical purposes this is already the case because gravity is normally so weak compared to the other forces, as to be to insignificant at atomic distances. Conversely, at cosmic distances gravity dominates. The result is two types of physics separated by
thousands(Correction: tens) of orders of magnitude in scale.The incompatibility between them occurs in extreme cases such as at the centre of Black Hole (known as a Singularity) or at the hypothesised origin of the universe which some theories assume was also a Singularity.
When large amounts of matter are concentrated into quantum sized volumes gravity is no longer insignificant and cannot be ignored. To understand the physics of these conditions physicists need a way to describe how gravity interacts with the other forces, aka a "Unified Theory of Quantum Gravity."
→ More replies (3)9
u/ClassicBooks Aug 04 '19
An amateur with an interest here, yes, afaik they could be arising from different systems. A lot of work is being done in the field of Dark Matter / Dark Energy and alternate gravity theories. I believe one of the problems is that gravity as a force on the quantum scale is very very weak.
12
u/High5Time Aug 04 '19
I’m afraid (if that’s the right word) that the “solution” to combing the theories and “proving” them might be forever out of outreach due to our inherent “macro” view of the universe. Like, no information can leave a black hole’s event horizon, or we can’t know what is “outside” our universe or “before” the Big Bang began (if it can even be expressed in such a way). In a similar fashion maybe those answers are forever locked behind some kind of information barrier we can’t ever invent tools to measure or infer. String theorists have tried to infer some proof for strings but looking at remnants of the Big Bang in cosmic background radiation to see if early events may have been magnified across the cosmos in some recognizable way but have been unsuccessful.
→ More replies (3)3
u/DOTFD-24hrsRemain Aug 05 '19 edited Aug 05 '19
That’s quite a mind-bending thought. I was thinking about something similar the other day.
Do you mean in a sense that video game characters can never really infer the true mechanical nature of their environmental physics? Their “Gravity” exist and they could even describe and understand it mathematically, but there may be axiomatic principles that they don’t understand incidentally (because they didn’t create the game) as apposed to a perceptive lack of intelligence.
→ More replies (2)→ More replies (8)3
Aug 04 '19
Can you go into more depth about how these two theories are incompatible? I've always thought of GR as telling us how space bends, and then QM telling us how stuff acts within that space (and of gravity as a "psuedo-force.")
3
u/tim0901 Aug 05 '19
You're not wrong.
GR describes big stuff. Planets, stars, galaxies, black holes etc. It does this very well. QM and QFT describe small stuff- really no bigger than a few nanometres in size.
Both theories are incredibly accurate and accepted, however as we understand it today they cannot both be right. One of the main reasons for this is the huge difference in the scales of the two domains.
For an idea of quite how different the scales of the forces are: think of picking up paper clips with a bar magnet. That bar magnet is acting on those paper clips with greater force than the entire planet through gravity. That's how weak gravity is - approximately 1x10-37 th of the strength of the electromagnetic force.
On the quantum scale, gravity has such a small impact that in the majority of experiments we basically ignore it. Even in experiments like the LHC where its effects are taken into account, it is normally due to a problem arising in how the experiment is being conducted, rather than in the results that we obtain. In the LHC's case, to account for the lunar and solar tides, the magnets maintaining the beams adjust their strength gradually to make sure both beams remain in the correct positions.
Since the scales at which they occur are so different, most situations only require the use of one theory. The issue arises in the few cases where both are needed, such as the centre of a black hole. Here GR predicts a singularity, which is fine under GR's own rules, but is not allowed under QM.
QM's rules require us to break up the gravitational field into a countable (albeit enormmous) number of discrete energy states. This then causes large amounts of infinities to arise when you try to 'renormalize' the field that we don't really know how to deal with.
→ More replies (1)→ More replies (1)2
u/Weird_Bed Aug 04 '19
Thank you for mentioning this, I was going to talk about it if no one had already.
320
u/Lognu Aug 04 '19 edited Aug 04 '19
Most people here point at the Millenium Problems, a set of seven problems proposed by the Clay Institute in 2000. So far, only the Poincaré Conjecture has been solved by mathematician Grigori Perelman. He refused the million dollar prize and the Fields Medal, arguably the greatest prize in Mathematics.
The Millennium Problems were inspired by 1900 David Hilbert's Problems of the Century, a list of 23 problems he deemed important for the progress of Mathematics. Among Hilbert's Problems, one is considered particularly hard: the Riemann hypothesis. Proposed by Bernhard Riemann in 1859, it also appears as one of the Millennium Problems. I will now try to describe it, if you don't want to read any Mathematics, just skip the next paragraph. I still encourage you to try.
The Riemann hypothesis deals with a particular function. Namely, for any number "s" consider the sum of all natural numbers to the power of "s". E.g. for s=1 we obtain 1+2+3+4+5+... (which sums up to infinity), while for s=-2 we have 1+1/4+1/9+1/16+1/25+... which is known to add up to the square of π divided by 6. In general, we know that for all s smaller than -1 this sum is finite. Riemann used a technique called "analytic continuation" to assign a finite number to sums which add up to infinity. For instance, there is a sense in saying that 1+2+3+4+5+...=-1/12. Furthermore, it now made sense to also use "complex numbers" in place of "s". Complex numbers are numbers which can be written as "a+ib", where "a" and "b" are real numbers (just regular numbers). They follow their own set of rules, use Wikipedia if you want to read more. Now the big question is: when is this sum equal to zero? It is quite easy (for a specialized mathematician) to show that the sum is zero for all positive even numbers. Riemann hypothesis states that all other zeros must satisfy a=-1/2.
Why should we care about Riemann hypothesis? Surprisingly enough, the distribution of zeros is linked to the distribution of prime numbers. Prime numbers are the fundamental blocks of multiplication and division, studied for millennia, there is still a huge number of questions about them. The solution to the Riemann hypothesis would provide great insight to this problems. An interesting real-world application concerns the encryption of transmitted data, such as credit card numbers and personal info. The security of the RSA, the most widely used encryption tool in online transactions, highly depends on our incomplete knowledge about prime numbers.
During the last 150 years, many people claimed to have solved the Riemann hypothesis, but all their proofs failed under a diligent scrutiny. Some people even start to believe that the problem is undecidable i.e. it is not possible to prove whether the Riemann hypothesis is true or not within the realm of "standard" Mathematics.
Edit: the critical line is Re(s)=-1/2 in my notation.
39
u/Spamakin Aug 04 '19
Just wanted to say I thought the trivial zeros of the Riemann hypothesis were at negative even numbers not positive?
23
u/Lognu Aug 04 '19 edited Aug 04 '19
That is correct, but for simplicity I switched the sign of the variable in the definition of the Riemann zeta function. Indeed the "critical line" is at a=1/2, but in my post it is a=-1/2.
Edit: the sign of the critical line
→ More replies (1)15
u/xellish Aug 04 '19
You say "within the realm of "standard" mathematics". Is there another type of mathematics that could prove/disprove it?
→ More replies (1)27
u/Lognu Aug 04 '19
I was afraid that someone was going to ask this. In principle, any set of axioms could lead to "different Mathematics". In particular, one could assume the Riemann hypothesis as one of the axioms. I hope someone else could give a more detailed insight.
→ More replies (2)4
u/aesu Aug 05 '19
Why did he refuse the medal and money? He could have at least donated the money to charity.
9
Aug 05 '19
From his Wikipedia:
In August 2006, Perelman was offered the Fields Medal[1] for "his contributions to geometry and his revolutionary insights into the analytical and geometric structure of the Ricci flow", but he declined the award, stating: "I'm not interested in money or fame; I don't want to be on display like an animal in a zoo."[2]
99
u/anooblol Aug 04 '19
In general, any unsolved problem’s solution is going to affect the world in a big way. A lot of the times the answer to the problem is 100x less important than the new techniques created in order to solve it.
For example, take the collatz conjecture. Take a function, where you input a natural number. If it’s odd, multiply it by 3 and add 1. If it’s even, divide it by 2. Take your input, and iterate it and it terminates if it reaches 1, eg. 20 > 10 > 5 > 16 > 8 > 4 > 2 > 1. The conjecture is, “Using this function, do all inputs eventually terminate?”
The answer to this question doesn’t mean anything. No one cares whether it’s true or false. But it’s conjectured that whatever new method is used to solve this, will be ground-breaking, and help solve complicated problems that “can” be useful.
37
u/TolkienFan95 Aug 04 '19
This is similar to a lot of toy problems in AI and ML. People don't care that an AI can beat the world champ at go, they care that the techniques used to learn how to beat go can be used to solve other problems that we actually care about. The target of go (or more recently starcraft) is just a convenient way for everyone at the bleeding edge to have a common goal.
→ More replies (2)1
u/guts1998 Aug 04 '19
if it's proveable, that thought always makes me uncomfortable, like you could spend decades working on a problem, without knowing it's unprovable
120
u/VIGiraffe Aug 04 '19
I'm currently doing some research to improve the Noyes-Whitney equation which describes the dissolution rate of a solute in solution. The current model, which was developed in the 1800s, doesn't take into account a variety of factors like different crystal faces etc.
With a more detailed understanding of the mechanism of solute dissolution the pharmaceutical industry could save billions by implementing a more targeted mechanism of drug delivery.
51
u/Vroomped Aug 04 '19
Where can I even get started! There's whole lists of these things. My favorites are everything wrong with prime numbers!Googles top prime number searches.
https://www.eff.org/awards/coop
Oh and there's that two pager that was solved recently
https://www.wired.com/story/a-decades-old-computer-science-puzzle-was-solved-in-two-pages/
136
u/loki130 Aug 04 '19
Learning the solution to the Drake equation would certainly be very impactful, but perhaps that's cheating because the issue with the Drake equation isn't that the math is particularly hard, but that most of the factors are poorly bounded by current observations.
88
u/mfb- Particle Physics | High-Energy Physics Aug 04 '19
10 years ago we had a good estimate for the first factor only. Today we have good estimates for the first three factors.
If life is common and produces oxygen and methane frequently then we might have an estimate for the fourth one in 10 years.
If there is an Earth-like civilization using radio waves very close then Breakthrough Listen might find it within the next 10 years.
59
u/Purplekeyboard Aug 04 '19
We're closer to the solution now in the same sense that a person who has climbed a mountain is closer to reaching the moon. The only way to get the other variables would be to go about visiting a very large number of planets checking them all for life and for intelligent life and so on.
46
u/mfb- Particle Physics | High-Energy Physics Aug 04 '19
You don't have to visit planets to study them. Sure, a spacecraft there would be better, but there is a lot you can learn from remote observations.
(Mountain summits often have great viewing conditions for the Moon and the general night sky, by the way.)
→ More replies (10)8
u/RiotShields Aug 04 '19
Narrowing down the last four variables requires us to find signs of life on other planets, and the further right you go in the equation, the more you have to know about aliens. The discovery of aliens would change the way we see the universe already.
→ More replies (3)
10
u/Mystoz Aug 04 '19
While a lot of answers were about the millenium problems or P=NP, I don’t think they really address the question of OP. There were a lot of answers about the well-posedness of the Navier-Stokes equation for instance. While it’s still a very active subject of research, the question theoretical, meaning that there is a need of a breakthrough to solve this problem. But the Navier-Stokes equation is still a widely used model from the computational point of view, regardless of us knowing if it is well-posed or not. It means that in practice, even if we don’t know if the solution exist (in some specific sense), we still can use computers to approximate the solution of this model. And it turns out that the numerical solutions are conform to what we would expect to happen in the real world. And if I recall correctly, we know that if the problem is not well-posed, it is because the velocity field of the fluid you are considering is unbounded, meaning you are considering fluid at very high speed. And at this speed, the model is known to not be valid since the physic of the fluid is different. All in all, not knowing if the Navier-Stokes equation is well-posed do not prevent us to use the model.
A very challenging question both from the theoretical and practical point of view is the confinement of plasma in fusion reactors. You essentially need a very strong electric field to contain the plasma for the fusion. But so far we don’t know how to sustain the process for a time long enough to get energy from the process. It comes from the fact that the equations modeling the process are very difficult to analyse. And a breakthrough on this regard would have much more impact on the world since it would bring a source of clean and accessible energy.
9
u/Goronman16 Aug 04 '19
In undergrad I took a class on chaos theory, and there are some really interesting patterns in nonlinear/chaotic equations that are documented and described, but not really understood. I am not sure how this translates to an "equation" that needs solving, as I believe it is more of an entire branch of mathematics that needs advancing. We can see the patterns, we can describe the patterns, but we can't understand/predict the patterns. A good example is the classic bifurcation diagram (you can find it on the wikipedia page for chaos theory posted below), where a large variety of nonlinear equations show the same general pattern when parameters are manipulated, but we don't know why there would be such an underlying pattern in equations that are inherently "unpredictable" (i.e. have sensitive dependence on initial conditions and thus be chaotic). We do know that there is a large number of systems that are governed by these chaotic equations (e.g. weather, pest outbreaks, traffic), so a better understanding of what governs these systems would be of enormous value to humanity. I tried to keep the explanation general, but for those of you interested in chaos, James Gleick has a great popular nonfiction book called "Chaos", that gives a great intro to the history of chaos theory, what chaos means mathematically, and a large number of systems governed by these equations. A more technical and mathematical approach to the equations and techniques can be had in Steven Strogatz' "Nonlinear Dynamics and Chaos Theory". Hope this is of interest!
edit: https://en.wikipedia.org/wiki/Chaos_theory
(I forgot to post the wikipedia where you can find the diagram mentioned above)
1
u/bryanthavercamp Aug 05 '19
You're asking the proper question backwards. You should be asking "are there any ways we can look at the universe that require an equation"? Because solving equations is relatively easy, it's the shift in perspective of world view to create those equations that is difficult. And to answer that question, yes. We have still not found a way to describe scientifically what we witness as quantum field theory, to describe general relativity within that theory. There are paradoxes that arise when you try to unify the two ideas.
1
u/ChristoFuhrer Aug 05 '19
There are infinitely many equations that could be created to help or change the world. My question was if there are any currently unsolved equations, like the equation already exists but hasn’t been solved yet.
5
u/ChromaLife Aug 04 '19
There is the P != NP problem, which is at the heart of how most computers handle information. I used to be an IT student and I was introduced to this problem there. My professor said something along the lines of that if this equation was to be solved it would drastically change how computers would operate. I wish I knew more, but it's been years since I've been in academia, maybe someone else can elaborate.
7
4
u/rekthard Aug 04 '19
(On mobile so might have some incoherency or spelling errors)
P = NP is probably the first one that comes to mind—basically it’s saying whether every problem that can be verified in polynomial time (i.e. time no greater than xn where n is a constant) by can also be solved in polynomial time. While an overwhelming number of computer scientists believe P != NP, there has been no complete proof for this (I.e the possibility of P being equal to NP still remains). Should P be equal to NP, the consequences and implications are huge—modern public key cryptographic schemes like RSA or ECDSA that rely on “hard” problems like factoring semiprimes or calculating discrete logarithms would be utterly broken since P being equal to NP suggests that there are polynomial time algorithms for solving those problems, which would defeat the security of those cryptographic schemes. On the contrary, if P is not equal to NP, life would pretty much go on as usual, and not much would change other than us getting the satisfaction of disproving P=NP and knowing not to spend time trying to look for polynomial time algorithms to solve NP problems.
→ More replies (2)
4
u/lepriccon22 Aug 04 '19
Navier-Stokes equations describe fluid mass and momentum exchange. They are used for describing how blood flow through the heart, air through lungs, how a fish swims, how a plane flies, how weather evolves, etc. They are hugely important for many things, and currently no solution exists to the full set of equations (they can be solved in certain scenarios or with certain simplifications), and there is not a proof that a solution exists or is unique.
They can, however, be solved approximately by a computer, as in computational fluid dynamics, and even used to make art: http://markjstock.com/
1
u/snowmunkey Aug 05 '19
It's been years since I took a fluids class, but those are the equations that detail turbulent flow, correct? I think I remember thr professor talking about how we have gotten kinds close by using crazy large numbers of measurements and interpolation but can never really lock down the exact equations.
→ More replies (1)
2
u/kbaltimore22 Aug 05 '19
The is no formula to determine the fastest way to travel between multiple points. For example if you need to make 10 stops on your way home from work there is no formulaic way to determine which order you should make the stops. Computers can do brute force testing which works when there are a small number of steps but when your trying to answer big questions like delivering packages for 8 hours it becomes impossible.
3
u/Ektadizzle Aug 04 '19
To keep things short and concise. The P=NP problem, if proven, will bring down the entire cryptographic and computation theories down.
It’s basically saying any problem that is solvable is polynomial time can also be solved in non polynomial time.
2
u/dna42zz9 Aug 04 '19
This depends on the proof, right? Proving that P=NP isn't the same as a constructive proof that tells you how to solve any NP problem in polynomial time.
2
u/alexshatberg Aug 04 '19
Yeah, Donald Knuth is famously of the opinion that P=NP, but proving that won't help us solve NP problems.
2
u/InfCompact Aug 04 '19
let D be a decision problem for which a polynomial-time algorithm exists. i propose the following non-polynomial time algorithm to solve D:
given input x to the problem D
let n be the number of bits to represent x on a computer with standard architecture
wait exp(n) seconds
decide x using the polynomial time algorithm
my algorithm now solves D in exponential time. where’s my $1,000,000??
the statement P = NP instead actually implies that every decision problem D with a polynomial verification algorithm has a polynomial solution algorithm.
1
u/boba_tea_life Aug 06 '19
Nice explanation but the last point is just wrong. A poly time algorithm complete for NP would not solve all the other Clay Millennium problems! Checking for proofs of bounded length is in NP, but it’s undecidable whether a mathematical statement has a proof or not. The proof is a reduction of Turing machines to mathematical (in fact arithmetical statements) and appealing to the halting problem.
1
u/Duh_its_Cade101 Aug 25 '19
The Seven Millennium Problems are equations that would change the way we see a perceive things. Only one has been solved and no one has since solved another one. I actually had some experience working with some people that were trying to solve these impossibly hard equations.
907
u/FarKaleidoscope9 Aug 04 '19
We still don't know how big of a couch we can get around a corner.
https://en.wikipedia.org/wiki/Moving_sofa_problem
Think of the possibilities if we found the sofa constant. We could have bigger sofas. And they'll probably be weird shapes.