## Physics Is (NP-)Hard 212

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.'"*
## No problem (Score:5, Funny)

I am NP-smart

## Re:No problem (Score:5, Funny)

## Re: (Score:2)

## Re: (Score:2)

As am I, but only on Saturday nights. I take the rest of the week off, as too much smartness is double plus ungood.

## Re: (Score:2)

On what basis do you claim the Universe is diagonal?

## Well no wonder I failed physics (Score:5, Funny)

I always thought it was hard, but that takes it to another level

## Re: (Score:3, Funny)

## Re: (Score:2)

I would pay to see a Schrodinger's cat fight. So suspenseful!

The over/under varies based on whether the cats are entangled.

Like horse-racing.

## NP (Score:2, Funny)

No Problem hard? I would have thought it would be harder...

## Re:NP (Score:4, Informative)

## Re:NP (Score:5, Informative)

Actually, NP stands for Non-deterministic Polynomial, i.e. An NP-complete problem can be solved in polynomial time in a nondeterministic Turing machine. In practice, this means that a candidate solution can be verified in polynomial time in a deterministic Turing machine (e.g. a normal computer). Normally this means the problem is exponential or factorial in a deterministic computer.

Now, NP-hard problems are those that are *at least* as hard as NP-complete, i.e. they need not be NP, so "polynomial verification" is not required.

## Re: (Score:2)

I would fully expect that verifying that a set of dynamical equations does indeed fit experimental evidence is in P so in this case (physics) the problem is NP-complete, certainly for classical mechanics. Verifying predictions in quantum mechanics may not be in P but is certainly in BQP.

## Re:NP (Score:5, Informative)

No, we don't know that yet (that's the whole P=NP debate). The thing we do know is that they can be solved non-deterministically in polynomial time.

## Re: (Score:2, Funny)

I don't know what the fuss is about: P=NP, where N=1.

## Re: (Score:2, Funny)

Obligitory http://xkcd.com/37/ [xkcd.com]

## Re: (Score:2)

Bzzt.

Non-deterministic polynomial.The rest is also incorrect. NP is an upper bound on difficulty, meaning that every polynomial problem is also in NP.

## Re:NP (Score:4, Informative)

No, NP-**hard** problems are by definition no easier than the hardest problems in NP. It's an open question whether P = NP in which case all NP-hard problems that are also in NP (that intersection is known as NP-complete) are in P as well.

## Re:NP (Score:5, Informative)

Attention: Car analogy in the last paragraph! Skip ahead, if you are bored.

If you can prove NP != P, then yes. In that case, you can not solve an NP-hard problem in polynomial time on a deterministic Turing machine. You can still solve it on a non-deterministic Turing machine in polynomial time though. And on an Oracle-NP machine, you can even solve it in one step; as those machines have an "Oracle" that can tell you the solution of an arbitrary problem in NP in one step.

There's a enormous zoo of complexities to sort problems into, from LOGSPACE, PSPACE, P, NP, PSPACE, NPSPACE, EXPSPACE, EXP, Oracle(P) all the way up to problems that are provably non-computable, like the Halting Problem.

But get this: All these categories have in effect a specific machine associated with them. For example PSPACE problems are those, that can be solved on a machine that needs a polynomial amount of memory based on the input size to solve a problem. LOGSPACE is the same, but with logarithmic space. CSPACE is the same with a constant amount of space.

Then you get to P, which does not care for space (indeed, the memory of the machine is assumed to be infinite), but it can only deterministically execute its program. If reading the symbol A in state B, it can only execute the action C -- and no other. If that machine can solve your problem in polynomial time (that is, polynomially many executions of operations with constant cost), then the problem is in P.

NP is the same, but now your machine may execute either action C

orD when in State B and reading symbol A, depending on a certain random variable (i.e. a coin-flip). If it does not need more than polynomially many of those "random" steps, then your problem is in NP.And now here's the nice thing: Every problem in P is also in NP. Why? Easy, because a non-deterministic machine can emulate a deterministic one; therefore, an NP-machine can trivially solve the problems a P-machine can by just following the same recipe (or emulating the P-machine).

But here's the difficult thing: Is it possible to create a P-machine that can emulate an NP-machine while still needing only a polynomial number of steps for each step of the NP-machine. After all, remember than n^c * n^d = n^(c+d). If both c and d is constant; (c+d) is constant and this n^(c+d) is still polynomial in respect to n.

The problem is, this reverse-question is damn hard to prove. But what you can prove is, is that there are certain problems whose solution on an NP-machine has a strange property: If you find a machine that can solve this problem on polynomial time, it can solve ALL OTHER NP-problems also in polynomial time; just by first rephrasing the desired problem to the problem it can actually solve. These problems are called NP-hard, because they are at least as hard as every other NP-problem. NP-complete problems are those whose results can be shown to be verifiable in P-time.

Thus, if you solve

anyNP-hard problem on a P-machine, you have shown that all NP-problems are solvable with that machine. If you can only show that the solved problem is in NP (but not -hard), then all you've shown is that the problem is a P-problem instead.As always, if you want to known more, ask Wikipedia.

If you want a car-comparison, though, maybe that will do: There are cars and airplanes. Airplanes can provably fly, drive around and transport cars; we think that cars can only drive around and transport other cars (and some small airplanes). If you can show that you can make a

flyingcar, that can transportanyairplane, you have shown that airplanes are not more than just strange looking versions of cars.## Re:NP (Score:4, Informative)

Minor correction due to it being far too late over here for perfectly clear thinking:

NP-complete is actually a problem that solves all NP-problems (including NP-hard) and can be shown to be itself in NP. NP-hard removes the latter restriction, as any machine that can solve problems "harder than NP-complete" can trivially solve all NP-problems. So NP-hard encompasses more problems and is thus the broader category of problems. Please keep that in mind when reading my above posting, as its points are still correct, but showing P = NP-hard is much, much, much more difficult than showing P = NP-complete.

Of course, any single NP-hard problem might actually be "merely" an NP-complete one, in case we have just not yet found an algo that can execute it in NP-time.

## Re:NP (Score:4, Interesting)

To paraphrase and dumb it down a bit as explained to me: this problem has no solution that will solve all cases. Every case has a unique solution that has to solved more by trial and error.

The most common example it the traveling salesman problem. If a salesman has to drive to 5 cities, what is the best way to arrange the trip to use the least amount of fuel. Since the problem is NP hard, any solution found for 5 cities does not apply to 6, 7, . .

Ncities. Also any solution found applies to 5 specific cities. Changing the cities will require a new solution.## Re: (Score:2)

The most common example it the traveling salesman problem.

Every time I think I've got my head wrapped around the P/NP thing, I get an example that I sort of understand... sort of.

Could you perhaps rephrase an example that matches nerdier things, like brute-forcing a hash or something?

## Re: (Score:2)

## Re: (Score:2)

Basically, the optimization for each itinerary requires its own formula.

## Re:NP (Score:4, Insightful)

Congratulations, you're the first respondent to

notcorrect "non-polynomial" as "non-deterministic polynomial." (Personally I blame lazy professors.)There are lots of problems solvable by a deterministic Turing machine in polynomial time (I.e. problems known for certain to be in P) that still need unique solutions for each possibility, though. Think about searching a list: you have to go through every item until you find the right one; there's no way to do it that's easier. The point about the traveling salesman problem and other classic NP-hard (and their best friends, NP-complete) challenges is that you are working with finding

combinationsof items, and youmustcheck all possible combinations; there is no easier way. We haven't proven that there's no easier way (and not due to lack of trying, mind you), but there aren't a lot of people who seriously believe we'll find one.## Re: (Score:2)

## Re: (Score:2)

In case this actually slips anyone up: NP-hard [wikipedia.org] means that, given a large number of options, and an answer that is a certain combination or ordering of those items, every possible combination or ordering must be evaluated to figure out the correct answer. "NP" stands for "non-polynomial," e.g. an exponential or factorial function of the number of items used.

Not quite right, but close enough for government work.

NP stands for "Non deterministically polynomial". There is a mythical machine called a "non-deterministic Turing Machine". NP refers to problem that can be solved in Polynomial time on such a machine. Compare that to P, which refers to problems that can be solved in Polynomial time on a regular Turing Machine/Computer.

The Great Question is whether P=NP. That is, are all the NP problems also P? There is a group of problems - called NP-Complet

## Re: (Score:2)

"NP" stands for "non-polynomial,"

Actually "NP"-hard problems ARE polynomial. NP stands for non-deterministic polynomial. It is polynomial, but the grade of the polynomialis is not constant.

If the grade of the polynomial is not constant (ie. there is a variable in some exponent), it is no longer a polynomial.

## Re:NP (Score:5, Informative)

NP = can be VERIFIED in polynomial time by a deterministic TM ('normal computer')

equivalently it can be SOLVED in polynomial time by a non deterministic TM.

This is different than problems solved in non-polynomial time (e.g: exponential time). While it is not known if NP != P (i.e: if NP is really harder than P, as assumed), it is known that EXP > NP. So problems that require exponential time are in fact 'harder' than NP problems.

However, it's important to notice that the article states that physics problems are NP-Hard, and not necessarily NP-Complete. The difference is vast, since an NP-Hard problem doesn't have to be in NP. It can in fact even be an undecidable problem. The halting problem is both undecidable and NP-Hard.

## Re: (Score:2)

He explained it wrong. It's not about the constant, it's about using a non-deterministic Turing machine to solve in polynomial time.

## Re: (Score:2)

## Re: (Score:2)

It's polynomial time in a non-deterministic computer. But as far as we know, non-deterministic computers can't actualy exist on our Universe (a physics problem, but physics is NP-hard, so how would I know?).

In a deterministic computer (anything that does exist), the best algorithms we know for NP-complete problems (the "easiest" of the NP-hard class) take exponential time. There is lot of optimizing one can do on them, you can get some answers faster, you can reduce the subexponential factors, but we can't

## Re: (Score:2)

Obviously it says no such thing, since P!=NP isn't proven.

The -Hard part just says at least as hard as the hardest problem in NP. If P==NP then that would include determinstic polynomial time problems.

## Re: (Score:2)

pedantic squared:

What you are describing are problems that are the intersection of NP-complete (NP problems whose solution can be verfied in polynomial time) and NP-hard (NP problems that are at least as hard as the hardest problem in NP).

AFAIK It is unknown at this time if all NP problems that are not also in "P" are NP-complete or if in the set of NP problems, there are some that are "simpler" than NP-hard problems that are still not in "P", and there is yet a subset of those that still cannot be verified

## Re: (Score:3)

whythere are complexity classes beyond NP-hard. And besides, who are we to deny others the satisfaction of making a sound correction?## It's not just dynamic... (Score:3)

It's chaotic!

## NP-HARD Mapping (Score:3, Insightful)

## Re: (Score:2)

Grab a pair of shoes and start walking. Let us know when you've solved the travelling salesman problem.

Found him! He's right now in Garmisch-Partenkirchen. Well, that was easy enough.

## Ow, my brain (Score:5, Funny)

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.

## Let me try to explain (Score:3)

"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 w

## Meaning all theories are approximate... (Score:2)

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. :)

## Re: (Score:3)

## Re: (Score:2)

Actually, it sounds to me like we need to be MORE suspicious of computational solutions. Humans take a bunch of shortcuts and make assumptions to derive equations from data (looking for an underlying theory is one of these) and so far they've served us well.

## So, back to statistics (Score:2)

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.

## What ISN'T NP-Hard? (Score:4, Insightful)

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!## Re: (Score:2)

the result is very useful.

one example is that it can be used to determine some minimal characteristics of an intelligent system, if by intelligent you mean something that acts based on an inner model of its environment.

i.e. you can't make an intelligent machine with a fixed number of "CPU cores" (unless P=NP).

## Re:What ISN'T NP-Hard? (Score:4, Informative)

Perhaps unfortunately neither factoring or discrete log are known to be NP-hard yet (fortunately) polynomial time algorithms have thus far alluded us although BQP algorthims (Shor's algorithm) have been found. Of course an NP-hard problem in BQP would be a major discovery. Also simulation of quantum mechanical systems (protein folding) is known to be in BQP, although no polynomial algorithm is known and it isn't known to be NP-hard. While its true that a great many interesting problems that apparently aren't in P but are in NP are NP-hard, but the above are examples of important problems that aren't.

## Re: (Score:2)

Determining if something is NP-Hard, is... wait for it.... wait for it...

NP-Hard!I don't think that's true. All you have to do is show that it's equivalent to another problem already known to be NP-hard. If you can show, for example, that a solution to the Traveling Salesman Problem would also be a solution to your problem, and vice versa, that's sufficient.

As for the value of proving it, one thing that knowing your problem is NP-hard does for you is that it tells you whether you're wasting your time trying to find a polynomial-time solution. Look, nobody knows for sure if P != NP, b

## No surprise (Score:2)

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 [wikipedia.org] says

the most notable characteristic of NP-complete problems is that no fast solution to them is known, which seems to apply here,## So simulation models are not as good as we thought (Score:2)

"we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem"Hmmm... dynamical equations for systems such as CLIMATE?

## Re: (Score:2)

This result says essentially nothing about the quality of simulation models, either for the climate or any other complex system. It applies to

exactlyreconstructing 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).## Re: (Score:2)

"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.

## Re: (Score:2)

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.

## Re: (Score:2)

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 da## Re: (Score:2)

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 approximationsthat 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.)## Re: (Score:2)

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 problemis 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

## Re: (Score:3)

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

identifythe exact dynamical laws that give rise to a set of observed data. This doesn't say anything about the computational complexity ofsimulatingof dynamical laws.Furthermore, this result says nothing about the quality (i.e., accuracy) or computational complexity of an algorithm to identify

approximatedynamical laws (e.g., computer simulations) from empirical data. For a## Timing is everything! (Score:2)

I'm glad I got my physics degree before they figured out how hard it is.

## Metaphysics (Score:2)

## Re: (Score:2)

## Re: (Score:2)

## Re:Metaphysics (Score:4, Informative)

Just because something is NP hard does not make it especially hard. NP-hard problems are only necessarily hard if the number of variables involved is high.

## Re: (Score:2)

they wouldn't say "what the f*** is that" if they'd seen it their whole lives. WE could be in the complex one. next question! :)

## Re: (Score:2)

## Hmm... (Score:5, Funny)

So these scientists were studying the science of physics itself, at some higher abstract level.

Does that mean this research is metaphysics?

## Re: (Score:3)

It is definitely metaphysics in the academic/philosophical sense.

However, metaphysics has come to colloquially refer to things like mysticism, spiritualism, etc.

http://websyte.com/alan/metamul.htm [websyte.com]

## Found the article on arxiv (Score:5, Informative)

"Determining dynamical equations is hard" by Toby S Cubitt, Jens Eisert, Michael M Wolf.

http://arxiv.org/abs/1005.0005 [arxiv.org]

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 [arxiv.org]

## durrr why is this news (Score:3)

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."

## Re: (Score:2)

## NP Does Not Stand For Non Polynomial (Score:5, Informative)

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....

## Not surprising at all... (Score:2)

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.

## Re: (Score:2)

So science is impossible?

Not, it merely says that it's difficult and will stay this way. If you want to prove that it's impossible you need to look in the direction of Godel's incompletude theorems...

## Re: (Score:2)

So science is impossible? duh, at least we have a theorem that says it.

Only if you believe our brains are congruent with Turing machines, which (adjusting flame resistant sunglasses) I do not.

## NP Hard ain't that hard (Score:3)

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 [dailygalaxy.com]

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 ...

## Re: (Score:2)

that might just say more about the type of English used in Engineering documents than it does about the ease of parsing

naturallanguage...Anyway, parsing natural language is not hard in the sense of computational complexity. It is hard in the sense that natural language is imperfectly modelled, requires a lot of context, varies between speakers, and has enough complexity to often seem irregular. Even humans can misunderstand natural language, despite being particularly good at language.

## "dynamical"? (Score:2)

"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)

## NP-Hard or not even computable? (Score:3)

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 [wiley.com]

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

## Assume a Spherical.... (Score:2)

America's population is approaching spherical. Perhaps they should call us "

NP-Soft", not NP-Hard.## Dynamical? (Score:2)

## No singularity then? (Score:2)

So apparently, computers are inadequate to doing physics - something Penrose [wikipedia.org] 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 bree

## Re: (Score:2)

## hahahaha! (Score:2)

dynamical

i'm myaat daaaaaymon!

## Re: (Score:3)

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.

## Re: (Score:2)

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 [nasa.gov].

## Re: (Score:2)

Clearly you don't understand how science works.

## Re: (Score:2)

Clearly you don't understand how science works.

Right, because I think that it has nothing to do with popular opinion, PR, and consensus.

## Re: (Score:2)

It certainly does have to do with those things, but it also has to do with real, actual science. False dichotomy.

## Re: (Score:2)

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 ex

## Re: (Score:2)

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.

## Re: (Score:2)

You are indeed a crackpot. Strawmen are fun, no?

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

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.

## Re: (Score:2)

It's not a religion, well, except for the deniers.

"Deniers"? Is that your religion's term for heathens?

## Re: (Score:2)

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.

## Re: (Score:2)

## Re: (Score:2)

I wondered how long it would take to bring up climate science. No climate scientist worth his salt would say it's

allbeen 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 argu## Re: (Score:2)

It might not. In any case, NP-hard doesn't mean unsolvable, it just means inefficiently solvable. Perhaps you are thinking of undecideability?

## Re: (Score:2)

If you average out the engineer's body's movement, you'll find that he has not, actually, traversed farther than half way to the treasure. Only a mathematician or physicist would consider the leading edge to be representative of the body, whereas an engineer would consider the centre of gravity to be representative (assume a spherical body... hey, no assumption required!), and thus there'd be no problem in reaching out to grab the treasure as long as his centre of gravity hasn't proceeded more than halfway

## Re: (Score:2)

## Re: (Score:2)

NP-hard doesn't mean it can't be "solved". It means there is a large number of solutions and finding the

bestsolution 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 meansonlycomputers can be used