Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Physics Is (NP-)Hard

Soulskill posted more than 2 years ago | from the assume-a-spherical-traveling-salesman dept.

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

Sorry! There are no comments related to the filter you selected.

No problem (5, Funny)

Anonymous Coward | more than 2 years ago | (#39148795)

I am NP-smart

Re:No problem (0)

Anonymous Coward | more than 2 years ago | (#39148863)

All you need to do is figure out the eigenvalues for everything, and the rest comes easy. The entire universe is diagonal.

Re:No problem (5, Funny)

Zero__Kelvin (151819) | more than 2 years ago | (#39148963)

Not Particularly?

Re:No problem (0)

Anonymous Coward | more than 2 years ago | (#39149443)

I am NP-smart

Not Particularly?

Barbie, is that you?

Re:No problem (1)

masternerdguy (2468142) | more than 2 years ago | (#39149323)

Fortunately making first posts isn't np hard.

Re:No problem (1)

lightknight (213164) | more than 2 years ago | (#39149397)

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

Here's the deal... (-1, Troll)

Anonymous Coward | more than 2 years ago | (#39148803)

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?

Well no wonder I failed physics (5, Funny)

the_humeister (922869) | more than 2 years ago | (#39148809)

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

Schrodinger's Cat Fight? (1)

Walt Sellers (1741378) | more than 2 years ago | (#39149901)

Does this mean that mathematicians set out to mathematically prove that their jobs are harder than physicists' jobs?

NP (2, Funny)

Anonymous Coward | more than 2 years ago | (#39148817)

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

Re:NP (4, Informative)

Samantha Wright (1324923) | more than 2 years ago | (#39148987)

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.

Re:NP (5, Informative)

timmy.cl (1102617) | more than 2 years ago | (#39149173)

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:NP (0)

Anonymous Coward | more than 2 years ago | (#39149519)

Actually this is often misquoted: it should be "non-(deterministic polynomial)", ie. that there is no deterministic polynomial-time algorithm to solve it.

Re:NP (4, Informative)

siride (974284) | more than 2 years ago | (#39149689)

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:NP (1, Funny)

slew (2918) | more than 2 years ago | (#39150069)

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

Re:NP (1)

John.P.Jones (601028) | more than 2 years ago | (#39149649)

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 (0)

Anonymous Coward | more than 2 years ago | (#39149217)

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

Re:NP (1)

johny42 (1087173) | more than 2 years ago | (#39149387)

"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 (5, Informative)

Anonymous Coward | more than 2 years ago | (#39149639)

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:NP (1)

siride (974284) | more than 2 years ago | (#39149713)

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:NP (1)

danm_cj (813009) | more than 2 years ago | (#39150109)

Well, NP actually stands for verifiable in polynomial time. Doesn't say anything about the time it takes to solve them. The -Hard part says that they definitely need more than polynomial time (of any degree) to solve.

Re:NP (1)

Arancaytar (966377) | more than 2 years ago | (#39149231)

"NP" stands for "non-polynomial,"

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 (0)

Anonymous Coward | more than 2 years ago | (#39149291)

Of course, NP-**hard** problems are by definition NOT polynomial.

Re:NP (3, Informative)

Intropy (2009018) | more than 2 years ago | (#39150035)

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 (5, Informative)

Jappus (1177563) | more than 2 years ago | (#39150057)

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 or D 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 any NP-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 flying car, that can transport any airplane, you have shown that airplanes are not more than just strange looking versions of cars.

Re:NP (3, Informative)

Jappus (1177563) | more than 2 years ago | (#39150233)

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 (1)

rayharris (1571543) | more than 2 years ago | (#39149265)

"NP" stands for "non-polynomial," e.g. an exponential or factorial function of the number of items used.

Actually NP stands for "Non-deterministic Polynomial". See http://en.wikipedia.org/wiki/NP_(complexity) [wikipedia.org] .

Re:NP (1)

greatslack (1102201) | more than 2 years ago | (#39149279)

Slightly pedantic correction: For a problem to be in the class P means that a solution can be guaranteed to be found deterministically within polynomial time. NP-hard problems might have a deterministic polynomial-time solution for a specific instance, but it's not guaranteed for all instances. So, "NP" actually stands for non-deterministic polynomial, meaning that an answer can be verified in polynomial time, so if you get a lucky guess you could get a solution in polynomial time.

Re:NP (1)

slew (2918) | more than 2 years ago | (#39150261)

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 in polynomial time. I don't think anyone thinks that is likely, but AFAIK it hasn't been proven yet. If all NP problems happen to also be in "P" (NP=P), then all of NP is in P and the postulated set of problems is the null set.

Re:NP (3, Interesting)

UnknowingFool (672806) | more than 2 years ago | (#39149283)

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, . . N cities. Also any solution found applies to 5 specific cities. Changing the cities will require a new solution.

Re:NP (1)

RulerOf (975607) | more than 2 years ago | (#39149647)

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:NP (1)

DigiShaman (671371) | more than 2 years ago | (#39149763)

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

Re:NP (3, Insightful)

Samantha Wright (1324923) | more than 2 years ago | (#39150195)

Congratulations, you're the first respondent to not correct "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 combinations of items, and you must check 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:NP (0)

Anonymous Coward | more than 2 years ago | (#39149329)

Please stop beating the woman!!!!

Me too (0)

Anonymous Coward | more than 2 years ago | (#39148847)

I am also (NP-) hard.

It's not just dynamic... (2)

SwedishChef (69313) | more than 2 years ago | (#39148871)

It's chaotic!

Re:It's not just dynamic... (0)

Anonymous Coward | more than 2 years ago | (#39149033)

Chaos is as easy as it gets.
Try to explain order and you're in a whole different ballpark.

Ooopps... lots of maths but no book reading (0)

Anonymous Coward | more than 2 years ago | (#39148875)

provably: BAD
probably: GOOD

Re:Ooopps... lots of maths but no book reading (1)

Anonymous Coward | more than 2 years ago | (#39149131)

A mathematician, a physicist, and an engineer are brought into a large room and told to stand against one wall. On the floor of the room is a very precisely drawn grid; on the opposite side of the room are three sacks.

The three learn that each sack contains $1 million, and that the object is for each of them to cross the room and grab a sack. The only rule is that they must cross the room in half moves only. This means that first they can walk exactly half the distance from where they stand to the sack. Then, they can again walk half the distance from where they stand to the sack, and so on.

The mathematician stands still for a moment, then shakes his head.

"Distance = 0 will never be true."

And with a sigh of defeat, he turns, and walks out of the room.

The physicist stares off into the distance, and he, too, shakes his head.

"Time to traverse distance equals infinity."

And with that, he sighs in defeat, turns, and walks out of the room, joining the mathematician outside. Soon, they are joined by the engineer, who walks out of the room grinning, and holding all three bags.

"Sometimes, close enough is good enough."

(Quoted from here: http://msdn.microsoft.com/en-us/library/bb263911(v=vs.85).aspx [microsoft.com] ...but this definitely predates Microsoft)

Re:Ooopps... lots of maths but no book reading (0)

Anonymous Coward | more than 2 years ago | (#39149207)

The version I heard was slightly different, but IMO better:
s/sack/naked lady
Engineer quips "soon I will be close enough for all practical purposes."

Re:Ooopps... lots of maths but no book reading (1)

Tanktalus (794810) | more than 2 years ago | (#39149985)

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 between his previous location and the treasure. Mind you, if it's very heavy treasure, this may be more difficult.

Re:Ooopps... lots of maths but no book reading (0)

Anonymous Coward | more than 2 years ago | (#39150169)

And then the test leaders took the money and gave it to the mathematician for being correct?

Re:Ooopps... lots of maths but no book reading (0)

Anonymous Coward | more than 2 years ago | (#39149411)

You should read more books, preferably a dictionary. "Provably" is a perfectly cromulent word, it means "It can be proven" http://www.merriam-webster.com/thesaurus/provable

Another author confused about computability (0)

Anonymous Coward | more than 2 years ago | (#39148911)

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?

Re:Another author confused about computability (0)

Anonymous Coward | more than 2 years ago | (#39149215)

Well, except that proving that is... NP-hard.

Re:Another author confused about computability (1)

siride (974284) | more than 2 years ago | (#39149753)

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

NP-HARD Mapping (3, Insightful)

joelwhitehouse (2571813) | more than 2 years ago | (#39148973)

Could we then map NP-HARD computation problems onto real world physics systems to find solutions?

Re:NP-HARD Mapping (0)

Anonymous Coward | more than 2 years ago | (#39149157)

Could we then map NP-HARD computation problems onto real world physics systems to find solutions?

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

Re:NP-HARD Mapping (0)

Anonymous Coward | more than 2 years ago | (#39150039)

I thought we solved the traveling salesman problem with online shopping? Now the salesman doesn't need to travel anywhere.

Re:NP-HARD Mapping (1)

Bromskloss (750445) | more than 2 years ago | (#39150299)

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.

NP-Hard (0)

Anonymous Coward | more than 2 years ago | (#39148983)

Physics makes me NP-hard.

Bring in the socio/psychologists (1)

Urthas (2349644) | more than 2 years ago | (#39148985)

They've been doing this for centuries.

Ow, my brain (5, Funny)

Walt Sellers (1741378) | more than 2 years ago | (#39149007)

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.

Meaning all theories are approximate... (1)

gestalt_n_pepper (991155) | more than 2 years ago | (#39149061)

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:Meaning all theories are approximate... (2)

codeAlDente (1643257) | more than 2 years ago | (#39149627)

From the abstract, it sounds like this bit is new: "As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years)"

Re:Meaning all theories are approximate... (1)

ceoyoyo (59147) | more than 2 years ago | (#39150379)

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 (1)

G3ckoG33k (647276) | more than 2 years ago | (#39149081)

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.

That's not right... (1)

Anonymous Coward | more than 2 years ago | (#39149107)

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.

Exceptions (-1, Flamebait)

Curunir_wolf (588405) | more than 2 years ago | (#39149119)

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!

Re:Exceptions (2)

dkleinsc (563838) | more than 2 years ago | (#39149251)

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:Exceptions (1)

Curunir_wolf (588405) | more than 2 years ago | (#39149599)

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:Exceptions (1)

siride (974284) | more than 2 years ago | (#39149777)

Clearly you don't understand how science works.

Re:Exceptions (1)

Curunir_wolf (588405) | more than 2 years ago | (#39149937)

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:Exceptions (1)

siride (974284) | more than 2 years ago | (#39150119)

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

Re:Exceptions (1)

siride (974284) | more than 2 years ago | (#39149843)

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

frost) pi5t (-1)

Anonymous Coward | more than 2 years ago | (#39149123)

inDecisi0n and

What ISN'T NP-Hard? (3, Insightful)

VortexCortex (1117377) | more than 2 years ago | (#39149127)

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:What ISN'T NP-Hard? (0)

Anonymous Coward | more than 2 years ago | (#39149467)

Well, for one, there's more classes than just NP hard. There's also a difference between NP-hard & NP complete (& maybe NP [wikipedia.org] since it's unknown if P = NP or not). For another, all you've stated are hypothesis you believe are true & obvious. Hell, other people may even think they're likely true & fairly obvious. But until you've actually shown it mathemtically, you don't know that it's true.

Hell, it's unknown if P = NP or not. It's widely believed that it isn't. It's really plausible that it isn't. A whole lot of of modern computational theory assumes that it isn't. And yet people are still trying to prove one way or the other & it'll be a major result either way if it ever is.

Re:What ISN'T NP-Hard? (1)

chichilalescu (1647065) | more than 2 years ago | (#39149537)

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? (1)

AndOne (815855) | more than 2 years ago | (#39149561)

I'd love to know what you consider the most basic algorithms. There are entire classes of problems which are polynomial and are not "basic". I also think you don't understand what it even means to be NP-Hard (which is just the numerical version of being NP-Complete.) Also to show that something is NP-Hard is equivalent to showing something is NP-Complete, which means you show there is a Polynomial time reduction to another problem in the appropriate class. Seriously, how did this get modded insightful.

Honestly, I don't think you even begin to understand complexity spaces or how they work.

http://en.wikipedia.org/wiki/Complexity_class [wikipedia.org]

Re:What ISN'T NP-Hard? (1)

AndOne (815855) | more than 2 years ago | (#39149643)

Correcting myself, NP-Hard isn't just the numerical version of NP-Complete. But rather the set of problems which are at least as hard as NP. NP-Hard includes the numerical versions. Sigh.

The numerical version of many NP-Complete decision problems are often NP-Hard.

Re:What ISN'T NP-Hard? (0)

Anonymous Coward | more than 2 years ago | (#39150067)

Showing something is NP-Hard is not equivalent of showing something is NP-Complete. NP-Complete is a subspace of NP-Hard.

The Halting Problem is NP-Hard but not NP-Complete.

Re:What ISN'T NP-Hard? (0)

Anonymous Coward | more than 2 years ago | (#39149837)

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

That doesn't mean it's NP-hard, it just means you don't have a fixed formal language that you can call "English", so it doesn't even make sense to ask whether it's NP-hard or not. And actually, there are many polynomial-time parsing algorithms for both programming languages and human languages [wikipedia.org] .

Re:What ISN'T NP-Hard? (0)

Anonymous Coward | more than 2 years ago | (#39149919)

Determining if something is NP-Hard isn't NP-Hard.

There's a concept of reduceability. If you can express a problem in the form of an NP-Hard problem, this problem is by definition NP-Hard.

For example, the TSP (Traveling Salesman Problem) is NP-Complete. It can be expressed as a subset sum problem, which is also NP-Complete. All that is NP-Complete is also NP-Hard. If you find something that is NP-Complete, you know it's also NP-Hard.

What about things harder than NP-Complete? If you can solve something that is even harder than NP-Complete, then since NP-Complete is a lower-bound on NP-Hard, it must be NP-Hard as well. An example, as wikipedia will confirm, is the Halting Problem. You can literally prove the infinite regress of that problem very simply. Since an infinite regress harder than NP-Complete, the halting problem isn't NP-Complete but is NP-Hard.

Thus, what you said is false.

Re:What ISN'T NP-Hard? (3, Informative)

John.P.Jones (601028) | more than 2 years ago | (#39149971)

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.

No surprise (1)

mbone (558574) | more than 2 years ago | (#39149135)

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,

Dynamical (0)

Anonymous Coward | more than 2 years ago | (#39149151)

Anyone else read this word and not believe it was a real word at first?

Re:Dynamical (0)

Anonymous Coward | more than 2 years ago | (#39149263)

no.

So simulation models are not as good as we thought (1)

mbeckman (645148) | more than 2 years ago | (#39149153)

"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:So simulation models are not as good as we thou (1)

Ambitwistor (1041236) | more than 2 years ago | (#39149437)

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

Re:So simulation models are not as good as we thou (1)

mbeckman (645148) | more than 2 years ago | (#39149835)

Really? Then why did the authors say:

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

The little boat of Simon Peter. (-1, Offtopic)

JCPM (2577407) | more than 2 years ago | (#39149163)

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

No new news (0)

Anonymous Coward | more than 2 years ago | (#39149267)

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.

Timing is everything! (1)

NEDHead (1651195) | more than 2 years ago | (#39149273)

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

Metaphysics (1)

Daetrin (576516) | more than 2 years ago | (#39149321)

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?

Re:Metaphysics (1)

masternerdguy (2468142) | more than 2 years ago | (#39149807)

Or maybe the universe as we know it doesn't exist with such bizzare laws. There might be other universes where f=sinma or something but we couldn't live there.

Re:Metaphysics (1)

codeAlDente (1643257) | more than 2 years ago | (#39149909)

Interesting questions. Our sensory systems would be very different if light traveled slowly. The speed of light, and the ion channels in our brains that convey patterns of light, depend on the EM properties of free space. It might be like trying to swim at low Reynolds number. One treatment that I've found compelling is a mathematical approach to Occam's Razor. pdf here: www.sas.upenn.edu/~vbalasub/public-html/Inference_files/Preprint.pdf

Hmm... (5, Funny)

tool462 (677306) | more than 2 years ago | (#39149353)

So these scientists were studying the science of physics itself, at some higher abstract level.
Does that mean this research is metaphysics?

Re:Hmm... (0)

Anonymous Coward | more than 2 years ago | (#39149407)

Is metaphysics NP-Hard too? Let's study that... so it would be meta-meta-physics... I wonder if that is NP-Hard as well?

"dynamical" (0)

Anonymous Coward | more than 2 years ago | (#39149355)

"dynamical" is not a word. The word "dynamic" also does not appear in TFA. So don't use it.

Found the article on arxiv (4, Informative)

mattr (78516) | more than 2 years ago | (#39149363)

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

Here, we give complexity-theoretic solutions to both these open problems which lead to a surprising conclusion: Regardless of how much information one has gained, deducing dynamical equations is in general an intractable problem -- it is NP-hard. More precisely, the task of determining dynamical equations in general is equivalent to solving the (in)famous P versus NP problem [1]. If P != NP, as is widely believed, then there cannot exist an efcient method of deducing dynamical equations.

On the positive side, our work leads to the rst known algorithms for extracting dynamical equations from measurement data that are guaranteed to give the correct answer. For systems with few degrees of freedom, this is immediately applicable to many current experiments. And, indeed, the primary goal of many experiments is to characterize and understand the dynamics of a system.

durrr why is this news (2)

Dr. Tom (23206) | more than 2 years ago | (#39149563)

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:durrr why is this news (1)

codeAlDente (1643257) | more than 2 years ago | (#39150099)

Why is it so obvious that data defined on discrete spaces should follow the same laws as data defined on continuous spaces? On one hand, it seems intuitive, even perhaps obvious. On the other hand, it has previously seemed intuitive to me that Fermat's last theorem would be proven using the mathematics of integers, but instead it came out of complex geometry.

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

Anonymous Coward | more than 2 years ago | (#39149641)

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

This is oil exploration. (0)

Anonymous Coward | more than 2 years ago | (#39149677)

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.

And I thought it was.. (0)

Anonymous Coward | more than 2 years ago | (#39149703)

F-n hard

Not surprising at all... (1)

tjstork (137384) | more than 2 years ago | (#39149755)

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:Not surprising at all... (1)

dargaud (518470) | more than 2 years ago | (#39150111)

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

So, duh? (1)

chaboud (231590) | more than 2 years ago | (#39149773)

Since Aggregability is NP-Hard [utep.edu] , this should surprise exactly nobody (who reads papers on complexity).

NP Hard ain't that hard (2)

PPH (736903) | more than 2 years ago | (#39150243)

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

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?