Forgot your password?
typodupeerror
Science

Physics Is (NP-)Hard 212

Posted by Soulskill
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.'"
This discussion has been archived. No new comments can be posted.

Physics Is (NP-)Hard

Comments Filter:
  • No problem (Score:5, Funny)

    by Anonymous Coward on Friday February 24, 2012 @12:43PM (#39148795)

    I am NP-smart

  • by the_humeister (922869) on Friday February 24, 2012 @12:45PM (#39148809)

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

  • NP (Score:2, Funny)

    by Anonymous Coward

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

    • Re:NP (Score:4, Informative)

      by Samantha Wright (1324923) on Friday February 24, 2012 @12:55PM (#39148987) Homepage Journal
      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 (Score:5, Informative)

        by timmy.cl (1102617) on Friday February 24, 2012 @01:08PM (#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.

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

      • "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 (Score:4, Interesting)

        by UnknowingFool (672806) on Friday February 24, 2012 @01:18PM (#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.

        • by RulerOf (975607)

          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?

          • Generally we know that brute force can crack a password eventually. You only know the maximum time it will take to go through all combinations; you can't calculate how long it will take to actually guess the right password. Now if you know certain characteristics about the strength of the password (length, use of special characters), you can shorten the time it takes but the problem is still the same; you have to go through all combinations until you find the password and you can't predetermine how long i
        • Basically, the optimization for each itinerary requires its own formula.

        • Re:NP (Score:4, Insightful)

          by Samantha Wright (1324923) on Friday February 24, 2012 @02:13PM (#39150195) Homepage Journal

          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.

      • by bmacs27 (1314285)
        Why is Parent modded up informative? Mod down overrated.

        Also it's important to point out that NP-Hard does not necessarily mean the problem is in the class NP. It means it is as hard or harder than the hardest problems in NP. That is, if we had a magic box that could solve the general problem of finding the best dynamical equation to explain data in polynomial time, we could solve any problem in NP in polynomial time. They did not show that a polynomial time solution to NP-complete problems like 3SAT
      • by readin (838620)

        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

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

    by joelwhitehouse (2571813) on Friday February 24, 2012 @12:55PM (#39148973)
    Could we then map NP-HARD computation problems onto real world physics systems to find solutions?
  • by Walt Sellers (1741378) on Friday February 24, 2012 @12:57PM (#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.

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

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

    • 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)"
    • by ceoyoyo (59147)

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

  • by VortexCortex (1117377) <(VortexCortex) ( ... -retrograde.com)> on Friday February 24, 2012 @01:05PM (#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!

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

    • by John.P.Jones (601028) on Friday February 24, 2012 @01:59PM (#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.

    • 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

  • 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,

  • "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?

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

      • by mbeckman (645148)
        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.

        • by skids (119237)

          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.

          • by mbeckman (645148)
            Kate McAlpine, who wrote the story for Science Magazine, specifically says this is a statement from the team that wrote the paper:

            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

            • The whole point of the article is that such equations, upon which climate simulations do indeed depend, are not easily derived and may not be reliable in many cases.

              No, that's not the point of the article. The point of the article is that there isn't any fast algorithm that can derive ALL dynamical equations PERFECTLY.

              It is silent on which specific dynamical systems admit accurate approximations that can be efficiently identified from data. (This is, as I noted originally, very problem specific and depends on your quality metric and the granularity at which you want answers.)

            • by skids (119237)

              Kate McAlpine, who wrote the story for Science Magazine, specifically says this is a statement from the team that wrote the paper:

              You mean you personally called her up and asked her whether she was paraphrasing or quoting there?

              The whole point of the article is that such equations, upon which climate simulations do indeed depend, are not easily derived and may not be reliable in many cases.

              Wrong, the point of the article is that the generic problem is NP-hard, which says nothing about subfamilies of the problem. If we can safely eliminate part of the solution set based on known properties of the input data other than its values, then it would require an entirely new analysis to determine if a specific solution to that specific problem is NP-hard.

              Secondly, the point is that a non-quantum computer

        • 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 a

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

  • So now that everyone has got all the dumb jokes out of the way, this has me wondering. If this applies to both classical and quantum physics does that mean that figuring out F=ma was NP-hard? Is that in the sense that it _could_ have been a crazy equation with dozens of components? Are we lucky that nature seems to "prefer" the simple solutions? Or do the solutions appear simple because the simple things we compare them to are based on those laws? Could there be a universe in which if you chart the motion o
    • 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.
    • 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
    • Re:Metaphysics (Score:4, Informative)

      by skids (119237) on Friday February 24, 2012 @02:40PM (#39150555) Homepage

      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.

    • 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! :)

      • by Daetrin (576516)
        It's certainly possible there could be universes where they have even simpler laws and figure it out even quicker than we do. However it took us a couple thousand years to figure out gravity and the laws of motion, and that's just with the "simple" laws we have. Cro-magnon men also saw and experienced gravity and motion their whole lives, so why didn't they figure out F=ma? And why do you feel that with more complex laws it wouldn't take even longer to figure out? And do you disagree that if the more comple
  • Hmm... (Score:5, Funny)

    by tool462 (677306) on Friday February 24, 2012 @01:22PM (#39149353)

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

  • by mattr (78516) <mattr.telebody@com> on Friday February 24, 2012 @01:22PM (#39149363) Homepage Journal

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

  • by Dr. Tom (23206) <tomh@nih.gov> on Friday February 24, 2012 @01:35PM (#39149563) Homepage

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

    • 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.
  • by Anonymous Coward on Friday February 24, 2012 @01:40PM (#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....

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

    • by dargaud (518470)

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

    • by mbone (558574)

      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.

  • by PPH (736903) on Friday February 24, 2012 @02:17PM (#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 ...

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

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

  • by sugarmotor (621907) on Friday February 24, 2012 @02:57PM (#39150773) Homepage

    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

  • from the assume-a-spherical-traveling-salesman dept

    America's population is approaching spherical. Perhaps they should call us "NP-Soft", not NP-Hard.

  • "Dynamical" is the same as dynamic so why the unnecessarily long word? Unnecessarily long words contribute to global warming!
  • 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

    • by bmacs27 (1314285)
      Let's not get ahead of ourselves. Humans don't "do science" in this sense either. Just as we have "good enough" algorithms to solve traveling salesmen problems, we can come up with "reasonable approximations" of data. That's at least one view of what science is.
  • dynamical

    i'm myaat daaaaaymon!

As the trials of life continue to take their toll, remember that there is always a future in Computer Maintenance. -- National Lampoon, "Deteriorata"

Working...