Slashdot Mirror

← Back to Stories (view on slashdot.org)

Physics Is (NP-)Hard

Posted by Soulskill on from the assume-a-spherical-traveling-salesman dept.

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

33 of 212 comments (clear)

  1. No problem by Anonymous Coward · · Score: 5, Funny

    I am NP-smart

    1. Re:No problem by Zero__Kelvin · · Score: 5, Funny

      Not Particularly?

      --
      Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
  2. Well no wonder I failed physics by the_humeister · · Score: 5, Funny

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

  3. NP by Anonymous Coward · · Score: 2, Funny

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

    1. Re:NP by Samantha+Wright · · Score: 4, Informative

      In case this actually slips anyone up: NP-hard 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.

      --
      Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
    2. Re:NP by timmy.cl · · 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.

    3. Re:NP by UnknowingFool · · Score: 3, 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, . . N cities. Also any solution found applies to 5 specific cities. Changing the cities will require a new solution.

      --
      Well, there's spam egg sausage and spam, that's not got much spam in it.
    4. Re:NP by Anonymous Coward · · 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.

    5. Re:NP by siride · · Score: 4, 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.

    6. Re:NP by Intropy · · Score: 3, 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.

    7. Re:NP by Jappus · · 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 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.

    8. Re:NP by Samantha+Wright · · Score: 3, Insightful

      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.

      --
      Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
    9. Re:NP by Jappus · · Score: 3, 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.

    10. Re:NP by Samantha+Wright · · Score: 2

      Thanks, but it was a legitimate gaffe. My professors never spent enough time on the theory behind complexity classes, so I actually had less of an idea of what I was talking about than I thought; now I understand why there are complexity classes beyond NP-hard. And besides, who are we to deny others the satisfaction of making a sound correction? :) Live by the red ink, die by the red ink, as they say.

      --
      Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
    11. Re:NP by Anonymous Coward · · Score: 2, Funny

      No, we don't know that yet (that's the whole P=NP debate).

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

  4. It's not just dynamic... by SwedishChef · · Score: 2

    It's chaotic!

    --
    No one ever had to evacuate a city because the solar panels broke!
  5. NP-HARD Mapping by joelwhitehouse · · Score: 3, Insightful

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

  6. Ow, my brain by Walt+Sellers · · 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.

  7. What ISN'T NP-Hard? by VortexCortex · · Score: 3, 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!

    1. Re:What ISN'T NP-Hard? by John.P.Jones · · Score: 3, 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.

  8. Re:Exceptions by dkleinsc · · Score: 2

    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 /. Long live http://www.soylentnews.com/
  9. Hmm... by tool462 · · 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?

    1. Re: Hmm... by tool462 · · Score: 2

      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

  10. Found the article on arxiv by mattr · · Score: 4, Informative

    "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

    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.

  11. durrr why is this news by Dr.+Tom · · Score: 2

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

  12. Re:Meaning all theories are approximate... by codeAlDente · · Score: 2

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

    --
    He once inserted random mutations into his code, just so he could have the experience of debugging.
  13. NP Does Not Stand For Non Polynomial by Anonymous Coward · · 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....

  14. NP Hard ain't that hard by PPH · · Score: 2

    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.
  15. Re:Metaphysics by skids · · Score: 3, 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.

    --
    Someone had to do it.
  16. Let me try to explain by l2718 · · Score: 2

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

  17. Re:Schrodinger's Cat Fight? by c4tp · · Score: 3, Funny

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

  18. NP-Hard or not even computable? by sugarmotor · · Score: 2

    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
  19. Re:So simulation models are not as good as we thou by Ambitwistor · · Score: 2

    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.