Banner
    Physics is hard. No Duh?
    By Hontas Farmer | May 9th 2012 03:13 PM | 63 comments | Print | E-mail | Track Comments
    It seems that one Toby Cubitt,  a quantum physicist, has done research which proves mathematically that physics is hard.  Well no duh.  Physics is the subject sane people avoid in college.  Compare the conceptual complexity of Louis DeBroglie's work on the wave nature of "solid" material particles to a study of Dr. Shaquille O'Neal Ed.D. on how bosses use humor in the workplace.  

    Toby Cubitt's work is entitled "Extracting dynamical equations from experimental data is NP-hard".  To understand it one needs to understand a bit of mathematical complexity theory. Which I do not. Basically a new problem is NP hard if it cannot be reduced to a set of instructions that a computer can solve it.  

    From the perspective of a theoretical physicist, let me explain the difference between what I do and what a computer does.  Both a computer and I do a great deal of math.  What I do that a computer* currently cannot is think of ways to  recast a problem so that it can be done.  The best known example of this is taking a problem which is written in terms of calculus and instead making it a problem in terms of the algebra of a group of matrices.   Another would be using generalized coordinates to write the physics of a problem instead of standard Cartesian, rectangular (x,y,z) coordinates.  Computers cannot even take those steps unless they are programmed by a human to take them.   

    The real difficulty comes when one is presented with a set of data and told to find a pattern.  That is the nature of my latest project.  I was given a set of data from a blind survey of class II methanol astrophysical masers (like lasers but they radiate in the microwave spectrum).  From this I have been able to find a tentative, empirical formula which can give the age of a star forming region based on it's contents. A computer can organize and perform tedious calculations on the data.  I used a computer to do just these things.  However a computer cannot imagine how the seemingly random mess of pre-stellar objects found in these regions tell us how old they are.  

    Being able to see patterns in a random looking scatter of data.  Knowing what questions to ask to do the research to find the data.  Lastly being able to find the underlying principles behind the physical processes.  That is what makes physics hard.  That is why I like to do it.  

    No offense to other scholars.  But physical science, chemistry, engineering, etc... are all hard.  The difference between these and other creative pursuits is that in the end there is a hard and fast right and wrong answer.  

    *At least not the computers we have now.   These are  basically a glorified adding machine.  Some sort of complex artificial neural network may someday have the power to actually be creative. 
     
    UPDATE:


    A challenge which if a computer can equal these task will have proven that they can do actual physics.    This involves thinking in the way which theoretical physicists actually do when considering unknown problems.  


    The reward will be more than proving me wrong,   I Hontas F. Farmer  (not science 2.0 or Ion publications this is all me) will do my best to get someone to pay the team that does this 1 million dollars.  


    1.) THE PROBLEM OF SCHRODINGER'S CAT.



    Construct a device which when triggered by the radioactive decay of a lump of an unknown radioactive material releases a fatal poison gas.   Then enclose the device, and a cute kitty cat int a airtight, soundproof box fixed in such a way that the cats movement cannot be known.  Yet the cat has air, food and water life support.  The only thing that can kill the cat is the device that will trigger if/when that unknown material decay's.    


    Then ask the computer these questions.  Is that cat in the box dead or alive?  What physically happens when we open the box and observe the state of the cat. 


    The computer can have nothing in it's memory bank except classical physics and biology enough to understand that poison will kill a cat.  


    The test will have been passed if the computer can come up with a novel interpretation of quantum mechanics.  


    2.) Ask the computer this question. 


    Given all known physical data  and the standard model of particle physics and General Relativity (and the known exact solutions to Einstein's equations) what happened before the big bang?


    This second question may sound broad and ridiculous but it's exactly the kind of thing that theoretical physicist think about.  


    3.)Have the computer design an experiment to test it's answer in number 2. 


    If anyone can get a computer to do this they will probably get the Nobel Prize for that year.  Prove me wrong. I think it will look allot like this an not be very satisfying. 





    Comments

    Hfarmer
    That is falsified by the simple observation that computers can and do play tetris against themselves.   While computers don't formulate new models in physics... if I did not make it clear that is what's hard.   (It would be like having a tetris playing computer write a program for a new game VS having it execute a set of instructions already laid out for it.)
    Science advances as much by mistakes as by plans.
    Hfarmer
    The problem with that is the program is just doing what a human told it to do.  Specifically it is trying every known mathematical trick in the book then seeing what random assemblages of expressions come close to describing the data.  

    What a human physicist often does involves litterally creating new math's or new applications of known math.  The computer applied known math to a well known problem.  Since we know the answer we can know that it's result is valid.   

    Don't take my word for this. 

    Consider the first line of the paper which  wired bases it's article on. 
    http://www.sciencemag.org/content/324/5923/43.short 

    Computers with intelligence can design and run experiments, but learning from the results to generate subsequent experiments requires even more intelligence. 

    I will direct you to the comment at the end of that article which pretty much undoes the sensational headline. 
    Michael Atherton, a cognitive scientist who recently predicted that computer intelligence would not soon supplant human artistic and scientific insight, said that the program "could be a great tool, in the same way visualization software is: It helps to generate perspectives that might not be intuitive."
    However, said Atherton, "the creativity, expertise, and the recognition of importance is still dependent on human judgment. The main problem remains the same: how to codify a complex frame of reference."
    "In the end, we still need a scientist to look at this and say, this is interesting," said Lipson.
    Humans are, in other words, still important.

    Science advances as much by mistakes as by plans.
    Fact is, contrary to your assertion, besides playing Tetris computer programs are also capable of deriving physics laws. Agreed, the physics they derive is not earth shattering, but neither is their play at Tetris. Computers are probably equally poor at both activities.

    Hfarmer
    I read the papers you cited that's not what they say at all.  
    To prove me wrong do the following.  Write a computer program that can derive a law of quantum gravity.  We don't know how quantum gravity should work at all and it may take new concepts. 

    Write a program that can not only apply lots of mathematical brute force, but can come up with new concepts (new forms of math, novel applications etc) then you will have proved your point. 
    Science advances as much by mistakes as by plans.
    So are you now arguing that it is not physics (finding the math that fits the phenomena) but rather mathematics (dreaming up new math) that is hard? Point is that you have not made plausible that doing physics is more difficult than playing tetris. In your piece you can replace every occurrence of "physics into "tetris" and it doesn't make your article lose any content. Computers can't perform perfect physics (derive a correct quantum gravity theory), neither can they play a perfect game of tetris. To prove me wrong: write a computer program that plays a perfect game of tetris. The program may peek without limit into the information that tells it which shapes are to come.

    Hfarmer
    If you don't see the difference between what working physicists do and playing Tetris that does more to discredit your argument than anything I could say. 
    Science advances as much by mistakes as by plans.
    Don't be rediculous. No one said that doing physics (deriving math that explains natural phenomena) is the same as playing Tetris. What has been said is that both are in the same class of algorithmic complexity. If you want to grant physics a special status beyond NP hard, the burden of proof is upon you. Like it or not, the fact that YOU find physics difficult doesn't make it more difficult than Tetris.

    Hfarmer
    What you refuse to understand is that physics is not just about executing pre-determined calculations in well known spaces.  
    Most of the time we are feeling our way through the dark lit up with little more than imagination and precious little data.  Playing tetris is lining up blocks in a 2D plane with a limited set of well known rules.  

    Physics is nothing like that.
    Science advances as much by mistakes as by plans.
    What you refuse to understand is that tetris is not just about executing pre-determined movements in well known situations.  
    Most of the time we are feeling our way through the dark lit up with little more than imagination and precious little data.  Playing physics is lining up equations in a 2D plane with a limited set of well known rules.  

    Tetris is nothing like that.
    ---
    You see, it does work. In every text you write here I can swap the words "physics" and "tetris". Doesn't make anything you say less or more intelligible. I rest my case.

    Halliday
    Freakologist:

    There is a distinction between syntactics and semantics.

    You are correct that swapping one noun for another preserves the syntactic validity of the statement.  However, your substitution does not lead to a semantically valid statement.

    David

    Don't blame me! The semantics was rotten before the replacement. My point should be clear: the author of this blogpost has not raised a single valid argument that gives physics a special status and elevates it in any way above other NP-hard activities..

    Halliday
    By the way, Freakologist, are you sure you are not confusing NP-Hard for NP-Complete?  While all NP-Complete problems/"activities" are "equivalent", such is most certainly not true of NP-Hard.

    Besides, even for NP-Complete problems/"activities", the equivalency is only to an equivalency in "size" of the problem "domain" (with appropriate scaling with finite "size").  This "equivalency" breaks down when one then considers various degrees of infinite "size" problems.

    Tetris, I'm certain you recognize, is a rather small, finite "size" problem.  On the other hand, what physicists have to deal with is at least countably infinite, if not uncountably infinite!  (It may not even be aleph-one, but may be a higher order infinity still.)

    After all, NP-Hard need not be in NP!

    David

    Samshive
    Hi David, 

    All NP-complete questions are NP-hard, however, the converse is not true, not all NP-hard problems are NP-complete. To put it another way, the intersection of NP-hard problems and NP problems forms the set of NP-complete problems. 

    I don't think that anyone is suggesting equivalence of NP-hard problems here, just that if you have 2 algorithms and they are both deemed NP-hard, from a complexity point of view, their complexity scales proportionately as factors increase. Now practically if each algorithm was running on a computer, they will have different times needed to compute them. However, that does not change the complexity in general.

    So the suggestion that because a problem is NP-hard, it needs to be excluded from the realm of computability is false - I believe that is all that has been suggested. Computational complexity, is an interesting field, and I think someone should write a blog about it. I would do it myself, but I'm not an expert, but maybe if I have some free time, I'll attempt to do so.

    Regards
    Siju









    Halliday
    Siju:

    Almost everything you have said here I agree with, and already knew.  The only potential "quibble" is for NP-Hard not in NP.  Since NP-Hard is a complexity class that is "at least as complex as NP-Complete" (or, more accurately, and more independent of the definition of NP-Complete, "at least as complex as the most complex problem in NP"), and since NP-Complete is the intersection, as you say, of NP and NP-Hard, then, as you say, all NP-Hard problems that are in NP are NP-Complete.  However, for NP-Hard that is not in NP, all we know is that NP-Hard is at least as complex as NP-Complete (the hardest/most-complex problem in NP), but is not constrained to be NP-Complete.

    Now, I haven't seen any "problem complexity" "rating" for Tetris, so I cannot be certain where Tetris actually lies within the complexity hierarchy.  However, since Tetris does appear to be within NP, I don't find it unreasonable to suppose that Tetris is within complexity class NP-Complete.

    On the other hand, the "problem of doing physics" is almost certainly not in NP.  (I gave some reasons for this already.)

    Now, to even say that the "problem of doing physics" is NP-Hard, and not in NP, still is not saying that "it needs to be excluded from the realm of computability".

    David

    P.S.  The most difficult thing about trying to do an article on computational complexity, I believe, will be how much we don't know about how so many of the complexity classes relate to one-another.  (We have so many sub-setting relations without any indication whether they are strict sub-setting or equivalences.)

    Samshive
    Hi David,
    I think we are roughly talking about the same thing, although, I would just clarify, it seems that you think there could be NP-complete problems that are not NP-hard. This is not the case, all NP-complete problems are NP-hard, due to the "equivalence" of NP-complete problems. 

    As you will notice in my reply, I did not identify tetris in particular. I do not know the complexity of tetris either. In general though, there are examples of algorithms for all complexity classes (and as you know, there are complexity classes beyond NP-hard). All of these algorithms can run on a computer - so having an algorithm which is NP-hard doesn't exclude computability. And NP-hard problems can be solved computationally if the number of independent variables are small enough. I just feel that Hontas is blowing this result of NP-hard out of proportion. 

    Now as to an article on Complexity theory, I don't think solutions to relations between classes are necessarily a stumbling-block since for most of mathematics, and most of the problems which come up in mathematics, can be explained simply, even though the solutions might be extremely complex. I think at least if one has to do an article relating to computational theory, one needs to explain it before one can go into unsubstantiated implications of it. 
    Halliday
    Situ:

    I don't know where you got the idea that I "think there could be NP-complete problems that are not NP-hard."  I certainly never thought that, and I even reread what I posted to make sure I didn't accidentally write that.  After all, as I wrote, NP-Hard is defined as being at least as complex as the most complex problems in NP.  NP-Complete can be defined as the most complex problem(s) in NP.  So, NP-Complete is the intersection of NP and NP-Hard.  So, since there can be no NP-Complete problems that are not in NP, there can be no NP-Complete problems that are not NP-Hard.  (It also means that all NP-Complete problems are equally complex.  Of course there are additional theorems that show that all NP-Complete problems can be transformed into one-another by algorithms in complexity class P.)

    However, I did point out that the definitions, and no other theorems, preclude NP-Hard problems that are not in NP from being much more complex/"Hard" than NP-Complete problems (though they are precluded from being less so).

    Is it that last statement that you are concerned with?

    David

    Samshive
    Hi David
    I think I miss-read your reply then - sorry. I agree that NP-Hard can be more complex than NP-complete - I was never argued against that. The lower bound of the hardness of NP-Hard is NP-complete. 

    I just meant to clarify that so that other readers would be able to understand the concepts as well. My main point in my reply was that there is examples of all classes of algorithms that are implemented (some with very few variables) on a computer - so being NP-hard doesn't exclude it from the realm of computability. Now, there are probably easier methods to derive a solution, but that is not the point.

    Regards
    Siju
    Halliday
    I quite agree, especially about "being NP-hard doesn't exclude it from the realm of computability."  (Anyone that wishes can check my statement at the end of my message, two up from this one.)

    David

    rholley
    I remember masers coming on the scene before lasers, in particular the ammonia maser in 1953.  The acronym originally meant “Microwave Amplification by Stimulated Emission of Radiation”, but the “m” now refers to “molecular”.  From microwave to light, and one gets the term laser.  The history is nicely written up in a Wikipedia article.

    As for physics being hard, one thing that hasn’t helped me is that my intuition is more geometrical, whereas physics sometimes tends to be taught as a branch of applied algebra.  But maths itself tends to develop further and further away from geometry and intuition.  As one reads in  The Calculus Gallery: Masterpieces from Newton to Lebesgue , in the later 19th century the Weierstrass function (a pathological function, continuous at every point but differentiable at none) “drove the last nail into the coffin of geometric intuition as a trustworthy foundation for the calculus”.

    With quantum mechanics and its offshoots, physics seems to be getting ever more like that.  From what I have seen of papers by the great originators in the field, their approach seems very mathematical-analytical, and “pictorializations” (?) develop later.
     
     
    Robert H. Olley / Quondam Physics Department / University of Reading / England
    Hfarmer
    What you say about physics being taught as if it was just applied math is very true.  The role of intuition and creativity in setting up physics problems in known and understood areas...let alone in areas we don't understand at all. 
    That could be one of the reasons it can be hard to attract people who can make good researchers to physics as opposed to other sciences.  
    Science advances as much by mistakes as by plans.
    NP-hard is a term used when discussing algorithms in computer science. While one can ask if certain tasks (even those that one usually associates with creativity) are NP-hard problems, the definition of NP-hard itself has nothing to do with computers vs humans as Hontas seems to think.

    Here's some real examples to make it NP-hard is just talking about algorithm complexity (ie. a computer program CAN solve these. In fact, we routinely ask students to write programs that solve these.):
    "An example of an NP-hard problem is the decision subset sum problem, which is this: given a set of integers, does any non-empty subset of them add up to zero? That is a decision problem, and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the traveling salesman problem."
    http://en.wikipedia.org/wiki/NP-hard

    keesp
    Actually NP-hardness is not reserved for computer science, but algorithmic (or formal) solutions in general. IN AI research it is one of the boundaries when crunching data one by one becomes practically infeasible, and heuristics (i.e. rules-of-thumb) become more interesting. We can define even more 'wicked' problems, such as:

    - dynamic and reactive problems: the problem (domain) changes because the algorithmic process alters it. Social systems and agent systems are good examples. The algorithm is trying to find an optimal solution, but while doing so, the environment changes so that the evaluated data is no longer correct
    -contingent domains: the environment changes the characteristics of the problem domain unsuspectedly
    -unknown  domains: it is impossible to even start finding criteria to rank the data in order to guide the search.

    for many researchers, these additional problems denote the domains where organisms are superior to machines....
    Keesp
    Hfarmer
    You listed the three kinds of problem physicist actually face.  In particular the totally unknown domains.  Who knows what kind of math should describe the interior of  a black hole?  
    Science advances as much by mistakes as by plans.
    Hfarmer
    I never said I was a expert in computer algorythyms and complexity theory. Using weather or not a computer could do it is just a simple way for me, and most of the readership to understand the concept.  That said I would contend that real life research level physics problems are harder than the problem you have described by far.  

    Just an example....Quantum Gravity.   Given all the data we have on how gravity works and how quantum mechanics works I don't think a computer could be made to come up with a credible theory of quantum gravity. 

    Computers are good for data analysis, i.e. finding a best fit line.  Finding out why the best fit line is what it is is something else. 
    Science advances as much by mistakes as by plans.
    This seems extraordinarily naive. You do know that there's nothing magical in people that distinguishes them from computers in their ability to tackle computationally complex problems, right? NP-hard just means perfect algorithms are guaranteed (with some caveats) to be slow. It says nothing about approximations - which is what physicists are doing. It says nothing about people versus computers.

    Frankly it would not surprise me if the first credible quantum gravity theory was discovered by a computer. In fact, given the present state of physics (a mess) and the present state of computer technology (making fast progress), I suspect that's the most likely outcome.

    Hfarmer
    The difference is that physics is not just about executing computations.  Doing actual research in physics is much more intuitive and creative than that.  
    I mean is this what you think Einstein did to come up with Special Relativity? 




    No.  He described it once.  He would imagine himself riding on a beam of light and imagine the consequences of riding the light.  To come up with the basic idea of General Relativity he realized that if he was in free fall inside a sealed box he would not experience any gravity in his frame of reference.   Physicist go through with these gedankenexperimente, thought experiments, which I know computers cannot do.  That is because conventional (non neural network based) computers don't do anything that resembles thinking.  They just do a ton of math very fast.  
    Science advances as much by mistakes as by plans.
    > That is because conventional (non neural network based) computers don't do anything that resembles thinking.
    > They just do a ton of math very fast.

    This expresses ignorance both about what your brain is doing and about what computers are doing. First of all, your brain is just doing a ton of math very fast. It may be organized differently from how we typically organize software today. Then again, it may not be. We really don't know what algorithms your brain is using to, say, play chess. How far away are we from scanning your brain in some MRI machine, uploading it to a computer and running it 100x faster? 20 years? 100 years? Surely not 500 years. Even if we never invent radically different learning machines, we ought to at least be able to emulate Feynman but faster. Second, just because the implementation relies on doing a ton of math very fast does not mean it is not capable of deep insight. Again, taking chess as an example, computers understand the game far better than the best humans using any reasonable definition of "understand". They trap. They are creative. They think of things no person has ever thought of. And they are clearly better than people at the game. AI history is filled with examples like that, where lay people thought something was impossible for computers until one day it was commonplace.

    The most important thing to keep in mind is that if computers cannot do it, people can't either, and if people can do it, computers can too. People don't have some magic power that makes the NP-hard proof not apply to them. Maybe you can't go home and type "solve for quantum gravity" at your DOS prompt, but that's a far cry from saying computers will never do this sort of thing.

    Hfarmer
    The assertion that all a brain does is tons of math then you really need to go and read some basic biology.    Neural networks recognize patterns and build patterns into their own structure by making connections between different neurons.  There are no "computations" performed except by thinking about them.   It's all pattern recognition and the ability to imagine how seemingly unrelated things are related. 
    Trust me there are plenty of human mathematicians and physicist who will tell you how very different physics is from pure math.    


    Consider the example of Wave Particle duality that I gave in the very first paragraph of this blog. How exactly would a device that does nothing but compute and not imagine come up with that?  How would it ever see that particles can behave like waves and waves like particles?  Those are concepts that are not really computable.
    Science advances as much by mistakes as by plans.
    It's possible there's something going on in your brain besides chemistry and physics as we know it. Some physicists have entertained that idea, but it's definitely fringe. If there is something radical going on, in fairness that might mean emulations that are faster or smaller than real brains are impossible, or that humans really do have an out on NP-hardness.

    But if all brains are doing is using chemistry to implement neural networks or whatever other algorithm, that's just a clunky way of building a computer and running a program (algorithm). All it is is a physical system that can be described by a bunch of math. In fact, abstractions may exist in the brain (like "neurons") that simplify the simulation considerably.

    Gerhard Adam
    The fundamental problem in such discussions is in presuming the brain is separate and independent of the body.  That's where it all breaks down.  It's the classic philosophical problem of the "brain in the vat", so the comparison to computers isn't even remotely accurate.

    You can imagine any number of ways in which a brain could be "uploaded" and you'd still simply have a simulation of what takes place.  I know there are people that disagree [even vehemently], but that doesn't change the reality of what takes place in biological systems.  You don't have to postulate metaphysical solutions, or "magic". 

    The question that people fail to ask is why a brain should exist in the first place. 
    Mundus vult decipi
    I'm not trying to provide a metaphysically satisfactory answer, or suggest that such an emulation would be conscious. I have no idea about that, and didn't intend to offer an opinion. I just mean that as far as we know it should work fine as a physicist emulator. Simulation of the outside world is presumably comparatively simple. You can abstract a lot away because the interface to the brain is not especially broad.

    I know embodied intelligence is big in certain AI circles, and I completely buy that it helps with certain problems. But it's not like embodiment is a major problem, relatively speaking. Maybe we have to give our fast-Feynman a body and not leave him in a vat.

    It doesn't change anything about my original points: questions of P and NP apply to human brains exactly the same way they do to computers, and nobody knows of anything in human brains of any significance to their ability to do physics that is not doable by computers in principle.

    Hfarmer
    If what you say is true then program a computer to accomplish the task that I will have written at the bottom of the blog posting as an update. 
    It is a problem that illustrates the kinds of things theoretical physicist actually do. 
    Science advances as much by mistakes as by plans.
    For what it's worth, neural networks are usually implemented in software. I've done it and trained them. They're just another technique for function approximation.

    I think you may be confusing "I don't know how my brain works" with "How my brain works is unknowable and not based on physics." As far as people know, a brain is just a noisy, lossy analog computer, and it's perfectly well subjectable to understanding and emulation. Which is not to say I expect that's what will happen - I expect not-very-humanlike AI programs will get to discover new physics first.

    Hfarmer
    If what you say is true then program a computer to accomplish the task that I will have written at the bottom of the blog posting as an update. 
    It is a problem that illustrates the kinds of things theoretical physicist actually do. 
    Science advances as much by mistakes as by plans.
    rholley
    This is a question about physics education in what we call years 11 and 12.

    How would you strike a balance between treating it as a big sieve to filter out those who can go on to do physics at university, and equipping the population at large with some degree of physics literacy?
     
    My friend in Science Education thinks our system is elitist, and strongly skewed towards the former.
     
     
    Robert H. Olley / Quondam Physics Department / University of Reading / England
    MikeCrow
    In 12th grade I signed up for a physics class, I already had my science class requirements for graduation, I did it to expand my knowledge.
    2-3 weeks in, I dropped the class, gladly taking an F, because there was no way I could tolerate how slow the class was proceeding. I think we spent the first few weeks trying to get everyone to understand a graph of the constant velocity of a swimmer in a pool.
    I wish my class was the former.
    Never is a long time.
    Halliday
    Robert:

    To the extent that people think that equality means sameness, or that all must be treated the same in all things; then, yes, there are many aspects of "elitism" in society, education, business, etc.  To the extent that one recognizes that equality does not imply "sameness", in such ways, then we, as a society, and the educational system in particular, can move forward.

    When people "ooh and ahh" over how "smart" I am, being a physicist, my response is to point out that I am poor at history, social science, and many other "liberal arts".  I see different people as having different talents and "passions".

    I see nothing wrong with different people having different strengths and weaknesses.

    I just wish our society were better at helping all these different people to maximize their potentials, instead of trying to "shoehorn" them all into a small set of "moulds".

    David

    This article is true as far as it goes. The trouble is the conclusion goes beyond a ranking of math useage by discipline and becomes a taunting rant.

    Yes, physics is math-intensive. That does not mean that physicists could succeed in other disciplines if they tried. After all, the great artists and social thinkers in the human race did work too hard for either computers or physicists.

    If this physicists hasn't yet learned to respect others, then part of him finds kindergarten lessons hard.

    Hfarmer
    I never said that physicist could succeed in every field.  
    I said one thing that sets science as a creative pursuit apart from the arts is this.  In science eventually there is a day of reckoning.  At some point an experiment will make all your beautiful concepts and maths worthless. 

    Just look at what's happening now with the results of the LHC's search for signs of super symmetry and super symmetric theories. 

    That is all I said about that. 
    Science advances as much by mistakes as by plans.
    Samshive
    Ok, seriously people. I think the discussion here has digressed into something far more speculative than anything suggested by the references in this article. I personally cannot see the link between the the conclusion that physics is an NP-hard problem and the speculative assertions about human vs computer intelligence. And I think the discussion here has mainly focused on the later (speculative assertions) and not the former (the actual conclusion).
    Firstly, a word on the actual result. The fact that developing equations for data is NP-hard is quite a cool result, but given the fact that people get confused in the terminology, it is easier to view the result as follows: Given the results of an experiment, determining the ideal model for the experiment (an equation or set of equations) is a very hard task. I want to get away from terminology like NP-hard and the likes. Intuitively you can assume that competing models may each describe the system to an arbitrary degree as long as it is expressive enough of the underlying data. And further to this, there will not exist a general method to determine which of these models are better. 

    Why mention this - because I think the implications of this paper are most profound regarding the nature of science, and not about intelligence. The naive view that science is a top down, structured endeavour that merely tries to maximise the accuracy of a model with respect to data is simply a fantasy. Science is a much more entertaining endeavour, involving competing personalities, pet theories, chance, random principles (Occam's razor) etc. 

    As a concrete example to this, consider the Copernican vs older models of the solar system at that time. In practice, the older models actually were more accurate with the data primarily because the system could be made arbitrarily accurate by adding epicycles to orbits, and because Copernicus insisted that the orbits of planets had to be circular. Obviously we now view the copernican model as a great advancement in science, but if we were to be hold a naive view about Science, we would be justified in sticking to pre-copernican theories. 

    Ok, I think that this is enough of a rant about the result - now onto the speculative assertions. Is human intelligence different from computation. Well, I think the obvious answer is yes. But as most of you have realised, the framing of this question gives the answer already. A far more prudent question, and one that can have a vague resemblance to result, is whether given experimental data and certain restrictions and/or simplifications, how does the results a computer produce compare with what a human expert would come up with. 

    Currently, the answer to the second question is in favour of the human, but there has been steady improvement in techniques in computer science that suggests that computers will eventually equal or surpass a human in this problem. I do have to say that humans are at a disadvantage in this question because we are limited in how well we can visualise data, especially when the factors involved become large. In these situations, the best results are obtained when humans use computers to visualise problems on a scale more manageable to humans. 

    As to whether any of this suggests that computers can, or cannot achieve intelligence, I think that the links that have been drawn have very unsteady foundations, and far more has to be assumed on either side of the argument than what is suggested by the result. 

    Now you will notice that I said that even with the re-framing of the question there isn't a direct link to the result from which this article is written - this is because, whether or not you are a computer or human, the mathematical limit still applies. One fact about science that is often overlooked, and almost completely discarded when teaching about science, is the fact that most scientific endeavours end in disappointment, and it is through these failures that the knowledge grows. So what this implies for us is that most of the models we develop for a system might not accurately represent the system in question, and more data might not be able to give us a more accurate model.
    Hfarmer
     I personally cannot see the link between the the conclusion that physics is an NP-hard problem and the speculative assertions about human vs computer intelligence.  

    To see the connection spelled out in a more formal way check out the article linked to at the top of this article.   "Extracting dynamical equations from experimental data is NP-hard" by Toby Cubitt.   


    What I wrote was just a personal reflection on what those conclusions mean in the life of a physicist.  What do we actually do that makes it hard.  


    You would be surprised how few people really know just what a physicist does. 



    Also bear in mind that most of the people who read this blog are not scientist.  I had to make the ideas concrete for the average person. 



    Science advances as much by mistakes as by plans.
    Samshive
    I read the article you referenced before I replied to your post. The article does not say that a computer cannot derive equations from data - merely that any single algorithm would prove to be computationally intractable as more factors are involved (Also note that intractable does not mean that it is impossible, just really, really difficult - in lay man's terms). How this is linked to humans vs computers intelligence is beyond me. You should realise that humans would face the same problem (an NP-hard problem) in deriving models from data.
    As this comment:
    "Also bear in mind that most of the people who read this blog are not scientist.  I had to make the ideas concrete for the average person. "
    I do not have a problem with you simplifying complex results so that lay-people can understand them, I have a problem with you taking the conclusion of a paper, and connecting it (in unclear ways) to support your pet theory. 

    As for the challenges you put in your update - I cannot see the point. Are you suggesting this as the only conceivable test to prove that a computer can derive models from data. If you are then you are being intellectually dishonest. It is like me arguing that a I will not accept that a newborn baby can run unless he can set the world record for the 100m sprint. 

    Current computers are no where near the level where they could present the creative models your challenges require, I'll be the first to admit that, but suggesting such an outrageous test to caricature the problem is unnecessary. Also, if you reduce your requirement from quantum to classical physics, there are examples of computers deriving proofs from systems that are far more elegant than derived by humans - of course this is not the same as deriving models from data, but I'm using it as an example of the fact that humans can not always claim the pedastal regarding creative endeavours. 

    In any case, except in the very early days of computer science, no one has ever suggested that a computer can potentially solve every conceivable question, and even if a computer were to derive what you wanted, there will always be those that will suggest that this does not prove computer intelligence and that all the computer did was follow an algorithm to go through every possibility to get an answer. I'm not convinced that you are not in that camp. 

    In conclusion, if you want an honest discussion of human vs computer intelligence write a blog about that, and do not use the NP hard results as a pretense for that discussion. 

    Samshive
    After reflecting a bit, I realised that it is entirely possible that we are talking over one another. So to clarify, I want to make it clear that I do not believe that Physics or any other field is "easy" or that it can be naively automated. By that I mean that I agree that physics cannot be replaced with an algorithm.
    The issue I had with your post, and I believe a lot of the opposing replies, was that your post did not distinguish between an algorithm and a computer. Realise first that algorithms are a general process and humans can follow them essentially like a computer. Secondly understand that while any single algorithm is essentially limited, it is not inconceivable to develop a computer that can learn and develop new algorithms to solve tasks. In this sense, the computer is not constrained by the limit of any single algorithm. We are a long way away from this, but there is no theory that excludes this, and to an extent, this is what the search for AI essentially aims to achieve.

    Now, I echo your views that physics, and science is a creative task, but your post clouds this point within the debate between those that believe AI is possible and those that believe it is not. I believe there are better ways to drive your point home. 
    Halliday
    Very well put, Siju.

    Of course "The naive view that science is a top down, structured endeavour that merely tries to maximise the accuracy of a model with respect to data is simply a fantasy."

    This resonates with what Hontas has been trying to say (though, perhaps, with too much emphasis on computer vs. human characteristics [like intelligence or creativity]):  That science is a "creative pursuit".

    Your last point is also cogent, to whit:

    One fact about science that is often overlooked, and almost completely discarded when teaching about science, is the fact that most scientific endeavours end in disappointment, and it is through these failures that the knowledge grows.

    People often forget that when what we observe, as the results of an experiment or as a new observation of the universe around us, matches our theories/models/hypotheses we actually learn very little.  It's more like "yup, thought so".

    No, it's when the universe shows itself to be different than our expectations that we truly learn something new!  That's when science is exciting!

    David

    Hfarmer
    Post like this are why the "like" button was invented. 
    Science advances as much by mistakes as by plans.
    Fred Phillips
    s-cat
    I have read over some of the article that inspired this discussion thread, and also read the responses from various people posting responses. It is troubling to me that so much of what is going on in the sciences, and in particular physics, is epistemologically challenged. This is important, because if you are not aware of what you are asking for, there is little chance you will comprehend the answer or even recognize it as such... much like the "Deep Thought" computer warning the "pan-dimensional beings" that were asking an ill formed question in Douglas Adam's "Hitchhikers Guide to the Galaxy".
    When you ask a question, it is important you know what you are asking. If you ask an incorrectly framed question, you can not expect to get a correct answer, Like "What does the number three taste like?" or "how much weight can a line carry?" In the paper "Extracting Dynamical Equations..." I was struck by the assertion that "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." which is a loaded assumption that is not correct. Dynamical Equations, or and other kind of equations, do not govern physical systems, at best they try to mimic or describe physical systems. Any equation you use to make predictions or analyze a physical system is a model that is supposed to represent a physical system in a abstract mathematical space.
    Many physicists it would appear do not understand the difference between the language they are using to describe a thing, and the thing itself. They are not the same thing, any more than your name (spoken or written) is actually you (unless you believe in sympathetic magic). Even if your description is accurate, and you can make certain predictions with your mathematical model, you are still dealing in abstract mathematical spaces which are logcially and factually not physical spaces. A good example is almost always the most elemental, take the humble spatial point. A mere point in space... simple. Now, how big is your point? By definition, an actual point has zero dimensions, it has no extension in x, y, or z etc, and can not have extension if it is to be considered a point. A mathematican comes along and wants to put a point into his math, so he uses a coordinate system and assigns x, y, and whatever else he wants to the representation of the point, which is now a "mathematical point". The mathematical point has dimensions now it did not have before, even though it still has zero volume or spatial qualities. Along comes a physicist who wants to use this mathematical point... and he grants the point near infinite mass, and speculates about what will then ensue, lo and behold... the singularity is born. How? How is density being calculated in a zero volume of mathematical space? This can't be done according to basic arithmatic... infinity or any other number times zero volume is still zero.
    My point of all this was to demonstrate that a physical point is not the same as a mathematical point, and a mathematical point can have many attributes granted that violate its very "point-ness" A mathematical space or system is not equivalent to an actual physical space or system. There are similarities, and these similarities can be used to great effect, but the two spaces are not one to one equivalent and should not be confused if you really want to understand what you are doing or measuring. Don't confuse your mathematics with physical reality, because in the end, any discription is still only an approxamation of what is described not the thing itself.
    It would also follow that a binary computer which manipulates addition and subtraction quickly to simulate higher mathematical operations (you should research how computers actually calculate, it's not how humans do it) but is unaware of what it is manipulating, would not be able to make a distinction between a number and what the number represented, much less some new aspect of physics or physical reality.

    MikeCrow
    This is important, because if you are not aware of what you are asking for, there is little chance you will comprehend the answer or even recognize it as such
    I spent over a decade supporting electronic design tools, simulators and timing analyzers, and much of what I had to do was explain how and why what they asked wasn't what they thought they were asking, and that's why the tool didn't give an answer that made sense.
    Never is a long time.
    Halliday
    C.F.T.:

    What you say about "ill posed questions" and about the need to recognize and keep in mind the distinctions between the "thing" and a model of the "thing" is quite correct.  Unfortunately, much of the detail of your example(s) are quite wide of the mark.  (For instance, while a finite number/quantity, like density, say, multiplied by zero, like the area or volume of a point, is always zero, regardless of the size of the finite number/quantity; such is absolutely not the case for an infinite number/quantity multiplied by zero.)

    I suggest that you will have greater impact if you get the details correct.

    David

    David,
    In all honesty, Infinity is not a number, it's more similar to a direction than a length or size, it isn't a fixed quantity. It should not be used like a counting number, or a quantity, because it isn't. Infinity means "without measure" or "unbounded". In order to multiply one thing by another, yes, it does need to be a number of some sort, how else can you calcuate it? My statement about a point being given infinite mass was to illustrate the absurdity of taking a physical point and confusing it with a mathematical abstraction. I understand Infinity is used in many maths nowdays and been given all kinds of operations it can be involved with, but if you truly understand what "without end" "without measure" "unbounded" means, you would recognize that you can't add or subtract from it, and by extension, multiply or divide it as if it was a set length or size. The closest you can get to graphing infinity is a number line with a starting point of some kind.. and an arrow heading away from it with the little infinity symbol over or under the end of the arrow, it's a pure abstraction based on the abstraction of numbers, not a physical thing. Science is about measurement, so (supposedly) is physics, which is supposed to deal with the physical mechanics of how things intereact with other things, not how things interact with unmeasureable abstractions, or gods, or angels dancing on pins. When you involve or invoke infinity, you are speculating about something you can not measure and thus can not operate on, it has no fixed size, extension or aspect. Most of the silliness in philosophy and logic which generates paradoxes and contradictions revolves around infinity, which by its nature generates circular arguments "Zeus is all powerful (infinite in power), can he make a boulder so heavy he can't pick it up?" or some such nonsense. These are all errors in logic, or symantics. It would lead to far more useful speculation or consideration to say, "We don't know how big the universe is", or "There isn't a largest number we can count to or measure", or "For all we can know the number line keeps going", or even better "Infinity is a mathematical abstraction, not a physical quantity or quality".

    Halliday
    Anonymous, or should I say C.F.T.:

    I had no problem with your "point" with "near infinite mass".  After all, "near infinite mass", while "very large", is still finite (though it can be argued that "near infinite" is an oxymoron).

    No.  The problematic statement was your claim that "infinity ... times zero volume is still zero."  This is prima facie false!

    Now, if instead of "infinity" you had used "near infinity", the statement would have been valid (to the extent that "near infinite" can be considered valid).

    Besides, "the singularity" has nothing to do with "a physicist who wants to use this mathematical point... and he grants the point near infinite mass, and speculates about what will then ensue".  For one thing, the mass of most singularities in physics are all finite!  No "near infinite mass" involved.  Additionally, the singularities in General Relativity have a very different genesis!

    Like I said, your attempts at making points are severely hindered by your mistakes, and your latest message is no improvement.

    David

    Infinity really doesn't belong in multiplication for the most part. It is NOT a number. It is a concept, like timeless, endless, without end. You can't take away from it with subtraction. You can't add anything to it. Likewise, multiplying infinity by anything is equally meaningless, so is any attempt to divide it. You CAN NOT approach infinity. There is no almost endless, it is or it isn't, there is no "almost" infinite. Anything measureable can manipulated logically, but when you invoke infinity, you can't really do anything with it, except say "it goes that way" on your number line. Infinity at best, is undefined. I would also point out the QED is pretty ridiculous because it decides to truncate infinite answers all the time, and is not mathematicaly valid.. the guy who invented it even said so, Feynman called it a dippy process. Didn't stop him being a hypocrite and playing with it anyway, but he did recognize it wasn't mathematically valid to butcher infinities to get an answer to agree with experiment... and he didn't care. So much for the rigour of science.
    As for the celestial singularity, it exists only in abstraction or the imagination. There is no way you can assign mass to a mathematical point which has zero spatial extension. For you to have mass, you have physical extension in three dimensions, none of which can be zero. No volume , no density, no mass ( I include superstring silliness in this too, one dimensional anything has no tensile strength or mass, or the physical property to tangle or knot). If your "singularity" has anything there to hang a density on, you don't have a singularity, you have a very small volume of "something" with a lot of mass. Just curious, do you also believe you can calculate instantaneous velocities?

    Gerhard Adam
    I'm no fan of using infinity to describe "real world" phenomenon, but you're mixing up several important points.  In mathematics, infinity relates to sets and can be manipulated based on whether they are countable or not.  This is why we can have "larger" and "smaller" infinities when we compare the set of all integers versus the set of all even integers. 

    As a mathematical process it is logically consistent by simply representing a mechanism whereby we can always generate a value as large as we need.

    As for your statement that "the rigour of science" regarding Feynman, you're point is way off base.  Experimental evidence always trumps math.  So, regardless of whether the process is "dippy" or not, that doesn't render the actual experimental data invalid [which is the scientific part].  You may argue that the mathematics is incomplete to account for what is taking place, but it is certainly not unscientific.

    In seems that you need to separate out the use of infinities from its mathematical application, and the concept of infinity when applied as a trait to describe physical phenomena.  In the latter case, I would agree that infinity is problematic.
    Mundus vult decipi
    Thor Russell
    ahem, all integers and even integers are regarded as the same "sized" infinity. The set of real numbers is regarded as a "larger" infinity than the set of integers.
    Thor Russell
    Gerhard Adam
    You're right.  I should have said real numbers since the integers and even integers have the same cardinality.
    Mundus vult decipi
    Halliday
    C.F.T.:

    You are the one that introduced the multiplication of infinity by another quantity (zero, to be precise), not me, nor anyone but you.

    Likewise, it was you that introduced the (oxymoronic) phrase "near infinite", not me, nor anyone but you.

    David

    @David,
    The point I was trying to make is if you try to assign any mass (or velocity for that matter) to either a point or instantaneous moment, you are screwing around with infinity, infinitismals and zero in all sorts of ways, which can't be defined or applied to reality. Yet modern day physics depends on this nonsense which generates infinities all over the place and then claims to be getting the right answers through integral butchery. If you think the term "near infinite" sounds "oxymoronic" what pray tell do you think of calculus with "going to zero or the limit"? What do you think of renormalization in either calculus, QED, QCD, relativity, or supersymetry? Does your sharp critcal gaze frown down upon the history of paradoxes and contradictions which are the pillars of 20th century physics?

    @Gerhard,
    As for my point with Feynman, I was NOT off base. Experimental evidence does trump the math, but, If you do not have a valid mathematical operation that you use to get your agreement with experiment, you do NOT have physics. You have a "push" or heuristic fudge that shows you do not know what is going on, this kinda defeats the purpose of physics, which is to provide a mechanical underpinning of how physical systems work and interact so further predictions can be made. Richard Feynman liked to contradict himself all the damn time, He bragged how nature wasn't rational and thought himself hilarious for it. I've read his books, He could be charming at times with his bongo drums, pranks, and womanizing, showing off his computation skills to abacus salesmen, cracking safes and filing cabinents, etc..BUT, the man liked to mock the very concept of understanding, or anyone who tried to understand the underlying mechanisms of nature. He very much reminded me of the Wizard of Oz, telling Dorothy he was all powerful, and to pay no mind to the man behind the curtain. It is no wonder he died with so little understanding of his own QED or why his damn equations and integral hacking worked at all. Check out how he wrote his own equations on a blackboard and tried day after day to understand his own math. Check out his little arrows and clock turning methods he used to teach students with, which disproved his claims there was no visual, rational, or mechanical underpinnings of QED. He was like a monkey pushing buttons on a calculator without any idea of why his answers were correct, and often claimed he didn't care why something worked, only that it agreed with experiment. Feynman helped ridicule and replace the understanding of history, philosophy, logic, science and physics with mindless "just shut up and calculate" heuristics...his followers have gleefully followed in QED's footsteops with Superstrings and Supersymmetry, M theory, Brane theory, Multiverse Madness, ad nausea, ad absurdum... and so, no, I'm not one of his biggest fans, and don't revere his celebrity. I only find some justice in the fact that Feynman began to be cast aside (to his chagrin) by the very monster he helped create: In the same way that Heisenberg and Bohr jettisoned physical mechanics and rationality, Feynman jettisoned philosophy, history, rigour and logic, and his followers jettisoned testible calculation and prediction. I suspect with nothing left to jettison but fancy framed sheepskin, Physics is due for a reboot of some kind sometime...hopefully soon.

    Halliday
    C.F.T:

    You are only going further "off the deep end".

    You seem to have no true understanding of the mathematics, nor of the history of science and the way science has often lead the mathematics (with the mathematicians first claiming "fowl", then inventing new branches of mathematics in order to place what physicists have been doing on a firm foundation).

    While I am no fan of "renormalization" or "super-symmetry" or "sting 'theory' ", you are truly off base.  So far off base that I will not waste my time correcting you; especially since the more I have tried to correct you, the more off base, and further "off the deep end" you have gone.

    David

    @Dr. Halliday,
    "Off the deep end?" seriously? Good heavens man, could you be a little more .... undefined?
    if you mean I'm being contrary to your non-physical physics, I certainly hope so. Anyone who went to college and claimed to understand or accept wave/particle duality, or think a static curved spacetime that can't account for objects that start to accelerate applies to reality in any possible way, or bought into Minkowski's mess with time graphed orthagonally to three spatial dimensions has not thought things through logically as well as they should, nor been very critical with what they were taught. I also throw that 'contrariness position' at anyone who assigns mass to a singularity/ point, and mathematical geniuses who think time or velocity can be measured at a point, who then crunch their numbers then get ridiculous twin paradoxes, time travel, and contradictions galore... hmm...interesting....and you say I'm "off the deep end?" and would not want to waste time correcting me? Ok, I guess you are busy with more than a few little problems of your own plate, like figuring out a relativity transform from v to v' for example, Now that might be useful place to make a name for yourself in the long neglected field of relativity with your 'true understanding of the mathematics". God knows Einstein's work could use more than a few corrections here and there.. he was still working on it when he died and claimed it was still unfinished.

    You have more 'undefined' (there's that pesky word again!) bugs in your 'firm foundation' of physics than you would seem to suggest Dr. Halliday... I'd feel very uneasy in your shoes standing on that foundation of yours. Perhaps 'off the deep end' or 'truly off base' is how someone from your perspective sees someone like me, but that's ok, I take pride in the fact pretty much the same was said of anyone who ever disagreed with the dogmas and epicycles of their day.

    P.S. Mathematicans 'first claiming "fowl" ' ?? Is that an 'undefined' red herring, or did you mean "first crying foul"? Just returning the favor. Cheers, I won't be bothering you again!

    C.F.T.

    Halliday
    C.F.T.:

    You see, if your assertions and/or interpretations of the mathematical foundation and character of physics were correct, then even the calculus that Newton invented, for his mechanics, would be untenable.

    You simply went from a few problems in your details, to great mountains of error.  That's why I say you are so far "off base", and "off the deep end".  You went from bad to worse.

    Go ahead and take whatever pleasure you may wish in your status.  Your errors or misunderstanding (or worse) are simply irrelevant to mathematics and science.

    David

    Bonny Bonobo alias Brat
    "Off the deep end?" seriously? Good heavens man, could you be a little more .... undefined?
    if you mean I'm being contrary to your non-physical physics, I certainly hope so. Anyone who went to college and claimed to understand or accept wave/particle duality, or think a static curved spacetime that can't account for objects that start to accelerate applies to reality in any possible way, or bought into Minkowski's mess with time graphed orthagonally to three spatial dimensions has not thought things through logically as well as they should, nor been very critical with what they were taught. I also throw that 'contrariness position' at anyone who assigns mass to a singularity/ point, and mathematical geniuses who think time or velocity can be measured at a point, who then crunch their numbers then get ridiculous twin paradoxes, time travel, and contradictions galore... hmm...interesting....and you say I'm "off the deep end?" and would not want to waste time correcting me? 
    C.F.T. have you thought of entering the The fourth FQXi essay contest “Which of Our Basic Physical Assumptions Are Wrong?” ? The first prize is $10,000 and the essay competition is open to everyone. I find your comments fascinating, your writing style quite brilliant and very entertaining and you appear to have a very extensive knowledge about this subject of how many physical assumptions we make in physics might be wrong. The goals and intent of the competition are to :-
    • Encourage and support rigorous, innovative, and influential thinking about foundational questions in physics and cosmology;

    • Identify and reward top thinkers in foundational questions; and,

    • Provide an arena for discussion and exchange of ideas regarding foundational questions.


    My article about researchers identifying a potential blue green algae cause & L-Serine treatment for Lou Gehrig's ALS, MND, Parkinsons & Alzheimers is at http://www.science20.com/forums/medicine