Summary | Rationale | Images | Credits | Powerpoint Δ | Comments
| All Nuggets
P != NP as a law of nature.
What is a good explanation of natural phenomena? When is a scientific theory useful? Being predictive is essential to these. And if prediction in the given model is computationally intractable, it is probably wrong, since nature does not solve intractable problems.
Summary
The efficient version of the Church-Turing thesis asserts that the class P captures everything computable efficiently by reasonable means. This should certainly include all natural phenomena, which we can hope to integrate into our computers. Thus whenever some natural phenomenon seems to solve a problem faster than we can on our computers, we have a win-win situation. Either we can use it to enhance computation, or our scientific model of this phenomenon is faulty.
Quantum computing research is a perfect example of this scenario, in which we still don't know who "wins" - can we build quantum mechanical computers, or should we revise quantum mechanics. But more likely than not, the extremely efficient mechanism of protein folding cannot be used to enhance computers. Rather the NP-completeness of this problem in current models suggests that we need to modify them (e.g. the actual objective function, the allowed operations, and/or the set of legal inputs) to better explain that efficiency of nature.
Contributors and Credits
Avi Wigderson
Image Ideas
List ideas for possible images. You can also upload images you've found using a command like this Δ.
Comments
- to give feedback on this nugget, just add another bullet to this list.
- Changed "intractable" to "computationally intractable", "phenomena seem" -> "phenomenon seems". - Salil
- Tagline is very accessible, but title and summary probably only make sense to computer scientists - they assume reader knows what is P, NP, Church-Turing thesis, etc. I wonder if this nugget could be made more accessible. See the nuggets Efficient Computation in the Physical Universe and Making Economic Theory Tractable, which cover special cases (and are quite accessible to non-CS readers). - Salil
- I really like the idea of this nugget but I agree with Salil that it is just not understandable by the target audience. I think it needs to be rewritten with the level of scientific knowledge of the target audience in mind (because that would be easier for the author than editing the current version). Here are some points to consider when doing this:
- P, NP, intractable, Church-Turing thesis, computable, reasonable means, quantum computing, what protein-folding is and what it has to do with this, NP-completeness, and objective function all need to be defined and/or simplified.
- Some sentences are quite confusing. For example, see the sentence "Being predictive is essential to these."
- What do you mean by "winning"? (I know what you mean but I think the audience won't.) Please provide an obvious example of this.
- What is your motivation? What is the burning question you want to leave with the audience after they see your nugget? Make sure to emphasize this throughout and express your need for further research to answer it at the end.
I think you have a catchy idea here which will make a nice nugget. It just needs to be expressed at a significantly higher level. -- K. Y. Rozier
- I agree with the above comments. This is a very nice nugget, but at this point it is not accessible to non-experts. -- Petros
