Slashdot Mirror
Physics Is (NP-)Hard
An anonymous reader writes "New research at the boundary of physics and computer science shows that determining the dynamical equations of a system from observations of its behavior is NP-hard. From the abstract: 'The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this work, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP-hard), both for classical and quantum mechanical systems.'"
I am NP-smart
Fuck me raw. Yes, you heard me. FUCK ME RAW. I want you to whip out your HARD ERECTION and POUND MY ASS. Fuck me raw.
OK?
I always thought it was hard, but that takes it to another level
No Problem hard? I would have thought it would be harder...
I am also (NP-) hard.
It's chaotic!
No one ever had to evacuate a city because the solar panels broke!
provably: BAD
probably: GOOD
From the article: "That's bad news for physics students who hope that a machine can solve all their homework problems, but at least their future jobs in the field are safe from automation."
Do people not understand that the tractability issues with NP-hard problems also apply to humans?
Could we then map NP-HARD computation problems onto real world physics systems to find solutions?
Physics makes me NP-hard.
They've been doing this for centuries.
It seems it is nearly NP-Hard to understand the concept of "NP-Hard". Thanks to Wikipedia I now understand that I don't fully understand this.
I should think that turning observations into accurate equations is hampered by never knowing if you have enough of the correct observations to determine the correct equation.
Nothing new there, but perhaps we might all need to be a bit less fussy about physical truths. Sometimes an equation ginned up by a GA with no underlying conceptual "theory" is good enough, and as good as it gets. Not satisfying, but probably (and probablistically) true. :)
Please do not read this sig. Thank you.
So, back to statistics, again.
Where is the practical relevance, really? I think this comes as no surprising news. Engineers and scientists have used simplifications and shortcuts to model the world for millennia, and advanced statistics for decades.
In physics we're mostly interested in approximations and not the actual answers. And getting an approximation is much much easier... (come up with ANY yes/no rule, and start applying it everywhere---you'll be approximating *some* systems to a certain degree; and it's not hard at all).
E.g. "anyone who floats is a witch". Simple and easy approximation.
Now, coming up with good approximations with predictive power (e.g. relativity, quantum mechanics, etc.) that's tough... but then you got a whole gray area of stuff like string theory, that can be twisted whichever way to fit observations and predict things that even in principle can never be observed.
There are exceptions to this, of course. Earth's climate, for instance, has all been figured out. We have consensus. The science is in!. It's incontrovertible!
"Somebody has to do something. It's just incredibly pathetic it has to be us."
--- Jerry Garcia
inDecisi0n and
Aren't all except the most basic algorithms, up to and including polynomials, NP-Hard? I know the term's meaning, but stories about proving things are NP-Hard seem sort of useless to me. The English language, for example, is NP-Hard. Has this been proven? I don't know, frankly, I don't care, but it's easy to understand that it must be considering it evolves and changes as one analyses it... Much like any quantum or physical system, or even the English themselves.
Determining if something is NP-Hard, is... wait for it.... wait for it... NP-Hard!
I really don't see why this is surprising. Hasn't there been a long history of failed attempts to mechanize the reduction of lots of data into hypotheses ? Don't these generally run into a combinatorial explosion of possible hypotheses, which seems like a requirement for a NP hard problem ? As the Wikipedia article says the most notable characteristic of NP-complete problems is that no fast solution to them is known, which seems to apply here,
Anyone else read this word and not believe it was a real word at first?
Hmmm... dynamical equations for systems such as CLIMATE?
The symbol of Simon Peter is: "a little boat (and ... great fisherman!)".
The symbol of the 2 metal keys like this http://upload.wikimedia.org/wikipedia/commons/8/81/Emblem_of_the_Papacy_SE.svg is the symbol of fake authority for auto-profiting itself this pontifical harlot of Rome for nearly 2 millennia. And the announcement of the fake authority and of that is beneath it is abomination.
Jesuchrist said that he gave him the keys, but never said that of the 2 metallic keys.
The question now is, is Simon Peter in his place? (after of his possible martyrdom). If not then somebody will have to go there and to occupy its position, perhaps i'm, namely that who starts is who ends, that means that, the last body that is positioned should be the first, and all the saints who follow him will be saved.
Rome is not the rock you were looking for on which Jesuchrist will build the Church, nor the place to be accessible to the Kingdom of Heaven. Simon Peter knew it, i might do, but I will have to try it with my faith that has guided me. If you follow me then I'll lead the place for the saints can access to the Kingdom of Heaven.
During all that time, the fake authority has never had access to the Kingdom of Heaven, because otherwise if any, how is it that they do not know the aramaic that also is the first (native) language of Simon Peter?
Holy gentle, gentile saints, do you want to see the living angels? You will can have a chance if you abandon the evil current empire and follow me.
From now, the current symbol is: "a little boat", and not that of Rome and not that from Rome.
JCPM: i did decipher it! Now it will be my time of reacting myself for acting myself divinely!.
There were multiple studies on this. The whole "cellular automaton" / NKS and the studies preceding that, as well, in the 70s and 80s. So nothing new here.
I'm glad I got my physics degree before they figured out how hard it is.
So now that everyone has got all the dumb jokes out of the way, this has me wondering. If this applies to both classical and quantum physics does that mean that figuring out F=ma was NP-hard? Is that in the sense that it _could_ have been a crazy equation with dozens of components? Are we lucky that nature seems to "prefer" the simple solutions? Or do the solutions appear simple because the simple things we compare them to are based on those laws? Could there be a universe in which if you chart the motion of a falling body instead of a parabolic curve you get some kind of roller coaster ride, and all the Galileos and Newtons of that universe say "what the fuck is up with that?" and then go back to farming or alchemy or whatever?
Of course if you consider relativity it does get pretty complicated. If the speed of light was 5 m/s, so that we had to deal with relativity in our daily lives, would we ever have been able to get a start at physics as a mathematical endeavour? Or is it a "requirement" in the formation of universes or life itself that there be a range of physics in which everything behaves in a "simple" and "consistent" manner?
This Space Intentionally Left Blank
So these scientists were studying the science of physics itself, at some higher abstract level.
Does that mean this research is metaphysics?
"dynamical" is not a word. The word "dynamic" also does not appear in TFA. So don't use it.
"Determining dynamical equations is hard" by Toby S Cubitt, Jens Eisert, Michael M Wolf.
http://arxiv.org/abs/1005.0005
An earlier article by same team:
"The Complexity of Relating Quantum Channels to Master Equations" by Toby S. Cubitt, Jens Eisert, Michael M. Wolf
(Submitted on 17 Aug 2009 (v1), last revised 12 Sep 2011 (this version, v2))
http://arxiv.org/abs/0908.2128
This result says essentially nothing about the quality of simulation models, either for the climate or any other complex system. It applies to exactly reconstructing the dynamics of a system. It says nothing about the quality of approximations to dynamical systems (i.e., simulation models), or the difficulty in constructing "good" approximations (where "good" is, in general, application-dependent).
This is the kind of thing that gets published in "peer-reviewed" journals when there are only 2 reviewers who belong to the wrong field. It is an ancient result that given the output of even a finite state machine, you can't figure out which FSM is being used.
Determining the exact diff. eqs. used to produce a given continuous system output is so obviously intractable that it's clear the "reviewers" were physicists barking out of the wrong hole.
Can I use mod points to get an article removed entirely?
And to the poster who said "what about F = ma?" I'd like to point out that Newton was WRONG.
----
OP: O day and night, but this is wondrous strange!
"And therefore as a stranger give it welcome.
There are more things in heaven and earth, OP,
Than are dreamt of in your philosophy."
Every time complexity theory shows up on Slashdot about half the posts try to explain what P, NP, NP-Complete, and NP-Hard mean but fail horribly. I'm going to post this and hope it gets modded up, though I have my doubts.
Quick, rudimentary definitions:
P: Deterministic polynomial time. A problem is in P if there exists a deterministic polynomial time Turing machine that decides it.
NP: Non-deterministic polynomial time. A problem is in NP if there exists a non-deterministic polynomial time Turing machine that decides it. Note that deterministic polynomial time Turing machines are a special case of non-deterministic polynomial time Turing machines, so every problem in P is also in NP. NP DOES NOT STAND FOR NON-POLYNOMIAL! Half the posts on this article are going to say that NP stands for non-polynomial and that only exponential time algorithms exist for problems in NP, so I want to nip it in the bud immediately. If NP stood for non-polynomial then P != NP trivially. Another way of defining NP is to say that there exists a deterministic polynomial time verifier for every problem in NP. A deterministic polynomial time verifier is an algorithm that, given an instance of a problem and some extra piece of data (usually a potential answer), can decide the problem.
NP-Hard: A problem q is NP-Hard if there exists a polynomial time reduction from every problem in NP to q. Since reductions exist, if you found a deterministic polynomial time algorithm that solved q you would show that P = NP. Read up on Cook's theorem if you're interested in how arbitrary polynomial time reductions can be made from any problem in NP to Circuit-SAT (an NP-Complete problem).
NP-Complete: A problem is NP-Complete if it is both NP-Hard and in NP. There exist NP-Hard problems that are not NP-Complete.
Anyways, continue....
We make seismic echo soundings; then attempt reconstruction of the heterogeneous medium through which the waves have propagated. It's difficult. It's fun. It's rewarding. And we get to play with exotic computing machinery.
F-n hard
So science is impossible? duh, at least we have a theorem that says it.
Honestly, I'm not surprised at all... it's basically just saying that you can't figure out the nature of a machine that created a pattern of bits without having it to begin with. There are some cool implications.
This is my sig.
Since Aggregability is NP-Hard, this should surprise exactly nobody (who reads papers on complexity).
"any general algorithm that turns a data set into a formula that describes the system over time can't be simplified so that it can run on a computer"
in an upcoming issue of Physical Review Letters? Seems like simulation of complex systems like climate are NP-Hard, which cast serious doubt on the models employed by proponents of human-induced climate change.
Does this mean that mathematicians set out to mathematically prove that their jobs are harder than physicists' jobs?
So, what are these people up to?
http://www.dailygalaxy.com/my_weblog/2011/05/-crunching-the-cosmos-will-intelligent-computers-trump-human-einsteins.html
I love all the CS majors with their NP-hard, can't do that theorems. Back when I was working at Boeing, we had a system that could take plain English engineering documents, parse them into a knowledge base and generate automated system tests. It was originally written by a couple of flight controls (mechanical) engineers. Part of my job was to maintain it. Every damned CS guru that came by told us that natural language recognition was too difficult a problem to solve. Except that we had been doing it for years.
Awaiting a CS major to jump in and start screaming at me in 3 ... 2 ... 1 ...
Have gnu, will travel.
"dynamical", not dynamic? I know it's a trivial observation but it tends to affect the veracity of the author.
Is this (in your opinion) the correct verbiage? (just asking)
I killed da wabbit -Elmer Fudd
I see no evidence that the authors used this language, rather than the journalists.
Note that trying to apply this to large simulations, which do not actually yield formulas, but rather projections, is sophomorism on its face.
Someone had to do it.
Until next week's RnDNA / quantum / thingy cloud blade complex is spawned brainwasheting-space - in 3D. O Tempora, ...
"NP" is a class of problems; roughly it's the class of problems for which you can quickly verify whether possible solutions are correct. For example, factoring a large integer may be hard, but checking that a given factorization is correct simply requires doing some multiplications. Making a weekly schedule for a school subject to constraints (every teacher can only teach one class at a time, every classroom can only be used for one class at a time, Dorothy gets Wednesdays off ...) is hard, but checking whether a given schedule satisfies the constraints is easy.
Now some problems are easier than others. How do we make this precise? We say that a problem A is easier than B if, given a method for solving B efficiently we can use it to solve A efficiently.
Finally, a problem is "NP-hard" if it's "harder than any problem in NP" in the sense above. Now NP problems are believed to be generally difficult to solve [for example, the scheduling problem is believed to be difficult]. So a problem harder than all NP problems ought to be hard.
What the paper shows is that if you had a method for efficiently reconstructing the laws of physics from experimental data, then your method also be used to solve scheduling problems, factoring, and all other NP problems.
Except simulation is the inverse problem. Simulation is going from a model to a represenative data set, this is about going from a data set to model. This no more casts doubt on climate simulation than factoring being NP-hard casts doubt on computer's multiplying integers.
Mathematicians recognize a set of truly hard problems that can't be simplified, Cubitt explains. They also know that these problems are all variations of one another. By showing that the challenge of turning physics data into equations is actually one of those problems in disguise, the team showed this task is also truly hard. As a result, any general algorithm that turns a data set into a formula that describes the system over time can't be simplified so that it can run on a computer, the team reports in an upcoming issue of Physical Review Letters.
Strawman alert: Nobody has said simulations yield formulas. They use descriptive formulas, which are derived from empirical data such as weather statistics (temperature, humidity, air flow, etc). The whole point of the article is that such equations, upon which climate simulations do indeed depend, are not easily derived and may not be reliable in many cases. Thus the projections produced by simulations are not as reliable as we thought. Hardly sophomoric. GIGO
Marian B. Pour-El found that even linear systems can have non-computable properties. See "The Wave Equation with Computable Initial Data Whose Unique Solution Is Nowhere Computable", Marian B. Pour-El, Ning Zhong, example link, http://onlinelibrary.wiley.com/doi/10.1002/malq.19970430406/abstract
Obviously there's a huge gap between NP-hard and non-computable.
On the other hand, one cannot even take it for granted that the Halting problem is not decidable. Toby Cubitt and colleagues probably assume a certain amount of metaphysics. I imagine they only claim NP-hardness as opposed to NP-completeness because they have no NP algorithm to show?
S
http://stephan.sugarmotor.org
given this:
Unpredictability and undecidability in dynamical systems
Abstract: "We show that motion with as few as three degrees of freedom (for instance, a particle moving in a three-dimensional potential) can be equivalent to a Turing machine, and so be capable of universal computation. Such systems possess a type of unpredictability qualitatively stronger than that which has been previously discussed in the study of low-dimensional chaos: Even if the initial conditions are known exactly, virtually any question about their long-term dynamics is undecidable."
Most scientists assume without much thought that physics has no limits.
However, even a tiny bit of analysis shows it has both an upper and a lower limit of usefulness.
The lower limit is Planck's constant--Heisenberg's Uncertainty. When you move beyond this point, all your measurements are suspect and you end up with bogus interpretations that don't mean anything. Discovery of a new particle means you merely discovered a new particle; it doesn't mean your theory is correct. You disprove the theory with absurd reduction--only argue the truthfulness of quantum mechanics with a legitimate physicist: someone who has published an article in volume II or later of a scientific journal unequivocally proving the universe did not exist until he and his grad students measured it. Reduction Ad Absurdum.
The other limit is at the upper end. If there is no limit to figuring things out, then physics leads 'naturally' to chemistry and biology and that with enough effort, you could infer and create the laws of chemistry or biology or human interactions based on the laws of physics.
We already assume that is absurd but don't examine the idea in depth.
The easiest understanding occurs when you realize physics covers the whole universe but chemistry only occurs in the realm of planets--hydrogen fusing into helium is physics, not chemistry. The best proof of 'emergence' or new complex areas is from math. Figure out how we go from integers to fractions to irrationals to imaginaries based purely on the opposite of varieties of counting/adding.
Adding 1 gives you an infinite list of positive integers.
Inversing or subtracting gives you Zero and the Negative numbers.
Multiplication is just a faster more restricted form of addition but its inverse gives you fractions--the Rational Numbers.
Squaring something is just a more restricted version of multiplication but inversing it gives you the Imaginary numbers.
The various groups of numbers are considered drastically different from each other by mathematicians. They even result in different sizes of Infinity
I'm not one of those people who scoff at scientific research that confirms what they already "knew" but I'm not all that surprised by this. If you think about what physicists and other scientists actually do, at its core, it must reduce to some combination of constraint satisfaction, tree search or some other statistical search or optimization, all of which are NP-Hard in the worst case. Another prominent method that physicists use on some level, is probabilistic inference, which is also NP-Hard. Unless the knowledge comes from a supernatural insight, the quest to find a better physical model of reality must be subject to the same fundamental constraints that any other optimization problem is.
It's dynamic, not dynamical. Clearly these people skipped undergrad English.
Perversions in language lead to perversions in thought. Or more simply put, lack of attention to detail in language points to a general lack of attention to detail.
Fair disclosure: I am ESL too, except I actually bothered. And no, I am not an English major.
So the article said that NP problems are all part of one family of problems or just different forms of the same problem. It further says that because these problems are 'hard' they can't be solved by computers. I must say, my gut instinct is that turning this many problems, and problems of this level of importance into one problems is the first step in solving all of them at once. oh, and before you tell me about how we can't see how anyone would really solve the 'NP-hard', first tell me how your so much more clever than the people who told us we would probably never solve this. http://en.wikipedia.org/wiki/Fermat's_Last_Theorem
ok.
Comment removed based on user account deletion
This still says nothing about how accurate the resulting models are, only how difficult they are to derive. Technically, not even that, but how hard the derivation scales. How difficult it is to verify the resulting model is a different complexity, and unless they also proved physics is both NP-hard and not NP-complete, they've said nothing about that. Even if that were the case, the fact it has to do with scaling means specific cases may still not be that hard. Even if say it were expected to take 1000 man-years of work to derive the model, it might only take a single week to verify it for example.
For example, just because the the decision version of the traveling salesman problem is NP-complete doesn't mean we can't be sure if any given solution is reliable. The reliability of any solution found is quite easily checked and certain. And of course, such a proof doesn't cast any doubt on reliability of traveling salesman already working...
Relating physics to some other delicious item might make this discussion more satisfactory.
Really? Then why did the authors say:
They didn't.
Seems like simulation of complex systems like climate are NP-Hard
No.
I guess you're going to make me repeat myself here. Try to pay attention.
What's NP-Hard is an algorithm which can identify the exact dynamical laws that give rise to a set of observed data. This doesn't say anything about the computational complexity of simulating of dynamical laws.
Furthermore, this result says nothing about the quality (i.e., accuracy) or computational complexity of an algorithm to identify approximate dynamical laws (e.g., computer simulations) from empirical data. For all we know, it's possible to identify approximate dynamical laws to a given system to an arbitrarily high accuracy, in polynomial time. They just can't be determined exactly.
Finally, this result has nothing in particular to do with any particular system, such as the climate, and it proves no results how hard it is to identify dynamics as a function of system "complexity". It's a statement about the ability of a single algorithm to identify all possible dynamical laws in all possible systems from all possible data.
which cast serious doubt on the models employed by proponents of human-induced climate change.
It sounds like you have an ideological axe to grind here. It's apparently not climate models per se you have a problem with, but the fact that they're employed by "proponents of human-induced climate change".
The theorem doesn't say that identifying climate dynamics from climate data is any harder or easier than identifying gravitational dynamics from trajectory data, chemical dynamics from molecular data, etc. It just says that there isn't a polynomial-time algorithm that can identify dynamical laws from measurements of every possible system.
NP-hard doesn't mean it can't be "solved". It means there is a large number of solutions and finding the best solution is hard. But finding a single solution isn't necessarily hard. In the case of physics finding a poor solution is trivial, in fact people come up with them all the time. NP-hard means we're doomed to find progressively better approximations, but will likely never find a perfect expression. This also has nothing to do with computers; in fact NP-hard often means only computers can be used to generate progressively better solutions (i.e. search the solution space).
Also it has nothing to do with Fermat's Theorem. That's about mathematical proof, not creating systems to model reality.
Finally, the summary says reality is a system "governed" by equations; this is clearly not correct. The system and its equations we use to approximate the behavior of reality are entirely abstract constructs. They exist in our mind as a high-order reflection of reality. They are a part of reality (since we are) but don't "govern" it any more than we do.
The whole point of the article is that such equations, upon which climate simulations do indeed depend, are not easily derived and may not be reliable in many cases.
No, that's not the point of the article. The point of the article is that there isn't any fast algorithm that can derive ALL dynamical equations PERFECTLY.
It is silent on which specific dynamical systems admit accurate approximations that can be efficiently identified from data. (This is, as I noted originally, very problem specific and depends on your quality metric and the granularity at which you want answers.)
America's population is approaching spherical. Perhaps they should call us "NP-Soft", not NP-Hard.
Table-ized A.I.
"Dynamical" is the same as dynamic so why the unnecessarily long word? Unnecessarily long words contribute to global warming!
If I used a sig over again, would anyone notice?
Kate McAlpine, who wrote the story for Science Magazine, specifically says this is a statement from the team that wrote the paper:
You mean you personally called her up and asked her whether she was paraphrasing or quoting there?
The whole point of the article is that such equations, upon which climate simulations do indeed depend, are not easily derived and may not be reliable in many cases.
Wrong, the point of the article is that the generic problem is NP-hard, which says nothing about subfamilies of the problem. If we can safely eliminate part of the solution set based on known properties of the input data other than its values, then it would require an entirely new analysis to determine if a specific solution to that specific problem is NP-hard.
Secondly, the point is that a non-quantum computer could not guarantee completion of the generic solution to this problem, though if the actual solution turned out to be on a short execution branch, it might spit out a definitive result nonetheless, perhaps even very quickly. But the formulas plugged into simulations are not derived from a generic solution, and they are not derived completely from computational statistics. They are derived from the combined grey matter and computational abilities of the scientific community, who have in fact solved many instances of NP-hard problems despite them being NP-hard, because they have background knowlege that helps them chop away vast portions of the problem space until it is tractable. Part of science is specifying a problem beyond its general family such that specialized solutions may be employed.
Arguing otherwise is like sitting around waiting for a ping-pong ball to quantum tunnel through the table.
Someone had to do it.
So apparently, computers are inadequate to doing physics - something Penrose famously claimed. If so, does this - as Penrose also claimed - prove that consciousness cannot be, at root, computational, since we can do physics (not speaking for myself here) fairly well?
Or to restate that, whatever our intelligence, in full, is, computers can't do it. Thus the whole prospect of the purported "singularity" is a mirrage - however much some may be taken in by it. There might be some similar prospect where we breed super-intelligent human beings - or dogs for that matter. But it's just not ever going to happen with machines.
Why? Because machines can't do NP-hard stuff.
"with their freedom lost all virtue lose" - Milton
These proofs always seem to fail to challenge their basic assumptions. Physics is likely to come from a subset of possible 'elegant' solutions and thus be identifiable in polynomial, or better time. The ability of physicists to do physics (and the manner in which they do it) would tend to hint that actually physics is not free to take any form but is from a smaller set. This is similar to why compression algorithms work, information is not devoid of redundancy and not all signals are equally probable, likewise not all physical laws are equally probable.
Sigh I'm sure lots of effort went into this but why can't mathematicians maintain perspective...
OK, "dynamic" is an adjective already. Adding "-al" does not make it another adjective. And no, I don't care if some obtuse dictionary writer accepts it.
Isn't the N-body problem already a stronger result than this?
Or are they orthogonal? I'm interested in any explanations about how they compare.
Disclaimer: IANAP and have not RTFA.
dynamical
i'm myaat daaaaaymon!
Comment removed based on user account deletion
Basically they are saying that even if you had tons of great and accurate data, the algorithm to process everything to generate the equations would prove to require too much time to compute. Like trying to crack AES 256 bit encryption or worse depending on the situation.
BTW, here's a pretty good link explaining NP a little better.
http://explorations.chasrmartin.com/2008/11/24/what-are-p-np-complete-and-np-hard/
Even Tetris game is NP-hard.
The reason why I brought up Fermat's Theorem, is that very well argued explanations of what we can't figure-out or do, supplied by very highly credentialed persons, has not been a barrier to actually solving problems. Fermat's is an example of something, that was generally felt to be unsolvable, for centuries, but then was later solved in a way that you could almost call kinda simple.
Making 100s of important problems into what is kinda 1 problem, is the first step in solving 100s of problems all at once.
Considering your argument, if I could turn the 100s of NP-hard problems into something that could be explained to a computer as one problem. I could run an algorithm against it, and from time to time, get marginally better results. Until, I just didn't care about the results being better. Once that is achieved, for me, the problem is solved. Once, most people just don't care about the slightly better results, it has been generally solved.
can't be solved, phish posh.
still being contrary, I suppose.