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
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.
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?
A particular scientific theory can be both well-proven and NP-Hard to determine. For instance, the process of determining that acceleration due to gravity is approximately 9.81 m/s^2 is NP-Hard. But that doesn't make the fact any less proven. That's because humans are smart enough to solve NP-Hard problems, and do so every day.
In other words, you're living up to your sig.
I am officially gone from
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."
A particular scientific theory can be both well-proven and NP-Hard to determine.
Yea, but I was referring to the AGW theory, not theories that can make consistent predictions. Before you can even derive a reliable equation, you need to understand and include factors in all the underlying equations and their ultimate effects.
Oops! Missed another one.
"Somebody has to do something. It's just incredibly pathetic it has to be us."
--- Jerry Garcia
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).
Clearly you don't understand how science works.
"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.
You are indeed a crackpot. Strawmen are fun, no?
Does this mean that mathematicians set out to mathematically prove that their jobs are harder than physicists' jobs?
Clearly you don't understand how science works.
Right, because I think that it has nothing to do with popular opinion, PR, and consensus.
"Somebody has to do something. It's just incredibly pathetic it has to be us."
--- Jerry Garcia
It certainly does have to do with those things, but it also has to do with real, actual science. False dichotomy.
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
What's fun is seeing how people react when you point out the flaws in their religion. They can't even take a joke!
"Somebody has to do something. It's just incredibly pathetic it has to be us."
--- Jerry Garcia
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.
http://www.youtube.com/watch?v=f8U_JveHS8E&feature=youtu.be&t=54s
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.
It's not a religion, well, except for the deniers, who will go to any length to stick their heads in the sand and distort, attack and otherwise misrepresent the complexity of the situation and the scientific findings thus far. It wasn't even a political issue until a bunch of conservitards decided that they didn't like the idea of giving up their precious oil-based lifestyle.
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
You are completely right. Things like gravity are well proven and yet we still don't know its true nature.
But, I'd wager that climate science still fits in the realm of NP-Hard and not well proven.
There is a lot of model work to be done before we call climate science well proven, heck I still think there are a lot of variables and feedback mechanisms that will need to be heavily studied and solved before we can even start on the well proven trail.
Don't get me wrong, I'm not saying global warming doesn't exist. I'm just defending the guy who was making a joke about "the science being settled" (no one should ever really say that).
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...
I'm not a conservitard, and I don't have a precious oil-based lifestyle. I believe in the goodness of preventing excess damage to our ecosystem in rational ways. However, I still take issue with the Global Warming cabal. Let me explain my position:
I see that there's some evidence of warming trends. I don't see anything other than mild correlation and guesswork that it's anthropogenically caused at all, and I certainly don't see any hard science indicating what percentage of it is anthropogenically caused versus a natural background warming pattern. Fundamentally, the problem of proving such things seems completely intractable, because we cannot accurately model our climate's recent past in sufficient detail, and extrapolations (even from good models) are always just extrapolations, they rarely match the reality to come. I still think it's a good idea that we curb our pollution output based on the available evidence, because it's prudent to do so. However, I don't believe there is anything resembling conclusive proof that largely-anthropogenic global warming is happening, and by extension I don't think there's anything resembling conclusive proof that any action we take will reverse any warming trend that may continue to occur over the next several decades.
Given the above, I can only assume that the unwritten thought process of the Scientific Community is this: Well, it's not really proven, but we think it's prudent to act anyways, so we're just going to try to convince everyone that it's proven beyond doubt so that they'll take action. It's basically lying to people that it's conclusive because you think they're too stupid to take the right course of action based on mere probability. They might be too stupid to otherwise take the right action, but that doesn't make the lie any more legitimate. Worse, the lie backfires, because even people who are too stupid to be prudent about the environment in the face of the current evidence are smart enough to see that you're lying to them. Science started a religious war here, and they're just as much religiously involved as the other guys...
I wondered how long it would take to bring up climate science. No climate scientist worth his salt would say it's all been figured out. What they are saying is that they've figured out enough of it, particularly the major factors, that they can make some reasonable projections about what's generally likely to happen under various scenarios. Now they've moved on to filling in details because they don't argue about most of the big things any more. Consensus is what happens when only the crackpots are arguing against it.
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.)
I hope you're ready. I'm really huge.
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.
It's not a religion, well, except for the deniers.
"Deniers"? Is that your religion's term for heathens?
I often don't like the choices people make, but I like the fact that people make choices. That's why I'm a conservative.
dynamical
i'm myaat daaaaaymon!
No, that's a reasonable term for what many of them are. I'm not necessarily talking about the scientist with a blog who's a skeptic. I mean the legions of regular folks and politicians who believe, for no good scientific reason, that global warming can't be happening, or if it is, it just can't be because of humans. If you want a religion, there's one right there.
Ok. I guess I was being silly. I thought you had borrowed a word that had come to be associated with "holocaust deniers" and used it to smear people who disagreed with you.
I often don't like the choices people make, but I like the fact that people make choices. That's why I'm a conservative.
Determining that acceleration due to gravity is 9.81 m/s^2 is easy. It's a linear least squares problem that is most definitely polynomial (and low order at that). Figuring out that F=ma is (apparently) NP-hard.
Comment removed based on user account deletion
So what's your term for the legions of regular folks and politicians who believe, for no good scientific reason, that global warming is happening, and that it must be because of humans? True believers? Fundamentalists?
Most of us don't have the data and time to decide whether global warming is happening, or whether it's a result of instrument error, misinterpretation of tree rings, etc.; and the further we go back, the harder the question becomes. (Well, maybe until the close of the last Ice Age.) So we take someone's word for it. We used to call such people priests, now we call them scientists. And since we can't validate their data, we rely on secondary and tertiary evidence to decide whether we believe. Secondary evidence might include consistency among different climate scientists, or whether specialists in fields like statistics find the climate scientists' use of statistics to be correct. Tertiary evidence might be judgments about whether their sources of income bias them (in either direction!), or whether they try to suppress contrary opinions.
If most of us must rely on secondary or tertiary evidence to decide *whether* global warming is happening, then it's even harder to decide whether it's caused by humans (or to what extent it's caused by humans). Certainly there are other possibilities, which we--and for that matter scientists--are largely ignorant about.
Personally, I think "skeptic" is a much better term.
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/
Considering that if some of the worst things that scientists think might happen do happen climate science deniers might be looked down upon in the same way holocaust deniers currently are in the future.
A skeptic is someone who really does look at the available evidence with a critical but open eye and who has the critical thinking skills to synthesize new knowledge and understanding from that, be it just for themselves, or for the world at large. The Fox News crowd does not generally fall into that category. They did not come to the global warming debate with the idea that it's a serious issue that must be examined critically and deeply. Instead, they come at it with the idea that it's all a big liberal conspiracy and can't possibly be true. That's not skepticism, that's just plain denial. There *are* skeptics (I mentioned that). A lot of the people who don't buy into global warming are not skeptics, but merely deniers. Likewise, there are people who buy into global warming without any critical thinking and so are just lemmings and bad in their own way. I won't defend them either.
Your middle paragraph makes a very dangerous and misguided point. There is, in fact, a big difference between a prophet claiming to speak for God and a scientist doing research and publicizing the results. The latter is actually verifiable. The latter's methods are public and known. The latter's methods must furthermore work and bear fruit. String theory gets laughed at here and elsewhere because it fails these things. And yet dogmatic religion last thousands of years despite countless pieces of evidence and arguments against it. No scientific theory would ever last that long if it had no truth value whatsoever. Bad science *does* get weeded out, even if it is politicized. In the end, there really is more value in coming up with the truth than just being right for the sake of being right. If global warming really is a big hoax, a big scientific blunder, it *will* be uncovered. Not through hacked emails or out-of-context quotes from a random climate scientist. It'll come out through actual, peer-reviewed science. Remember also that it's in the system's interest for global warming to be false. As such, any real evidence against it would have strong political backing.
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.