Summary | Rationale |
Powerpoint | JPG Slide |
JPG Image | Credits | Comments
| All Nuggets
The P vs. NP Question
Is finding solutions no harder than checking them? Can the ability to find good solutions ("creativity") become as routine as
the ability to appreciate good solutions?
Summary
P is the class of problems for which solutions can be found efficiently (in time that is polynomial in the length of problem description). NP is the class of problems for which solutions can be checked in polynomial time. NP contains P. Most experts believe that the two classes are different, but nobody has found a proof of this.
Rationale
If P=NP then creativity (in almost every conceivable discipline) can be automated. Cryptography becomes impossible. Trying to understand the relationship of P and NP seems fundamental to understanding computation. This question seems to be a problem about the notion of computation itself, not merely about a specific model (such as Turing machine).
Contributors and Credits
Sanjeev Arora
Image Ideas
List ideas for possible images. You can also upload images you've find using a command like
this Δ.
Image of beethoven (representing creativity).
Alternatively, Einstein standing before a class with E=mc^2 on the blackboad?
Comments
- In the tagline I'd say "as easy as" instead of "no harder than". The second sentence of the tagline doesn't work so well for me (somehow "good solution" doesn't sound that catchy). Rather than just rephrase the first one, maybe something along the lines of "The resolution of this fundamental question about computation will have great significance for numerous disciplines." - Salil
- I think it'd be good to move the current summary (which has a technical tone) to the rationale, and develop a summary along the lines of the beginning of the rationale --- describing the vast implications of P vs. NP that can be appreciated by a layperson. We should convey that a resolution in *either* direction is important; currently it says that we believe P != NP but only talks about how great it would be if P=NP. Either we need to say that we should consider the latter a genuine possibility until we have a proof, or also talk about how proving P!=NP would also open the door to a dramatically improved understanding of computation (as well as have applications in crypto, etc.). - Salil
- More implications of P=NP are "the best solution to any optimization problem can be found efficiently", "much of artificial intelligence and learning will become easy".
- We should probably tone down the creativity discussion (especially "in every conceivable discipline"). To generate great music automatically, we'd need not only P=NP but also to find the algorithm that recognizes great music (if there is one). It may be nice to use arts/literature as an analogy, but only as an analogy. - Salil
- Note from designer Elaine Park: It seemed to me that the least ambiguous way to represent the idea of "creativity" (especially as something which is difficult to automate) was to use the painter's easel and tools. A music composer might seem to work as well, but it may be hard to get the idea of creation (vs. musicianship) across as easily.
- I like the image. The second sentence of the tagline needs to be punchier, though. Perhaps replace it with "Can creativity be automated?" Of course this is a bit of a stretch, but then the summary (which is currently too technical) can explain what we mean more accurately. - Salil
- I like the image too and I think the easel is a good metaphor for "trying to find a solution". Is there away to add to the image a completed piece of art showing that it is not hard to identify a good piece of art. P is appreciating art and NP is trying to create it. It is close. - Richard
- the sentence "crypto becomes impossible" is too strong. re. modern painting... hmm... sometimes it seems that appreciating it takes more work than creating it.. :-) - Bernard
- Revised ppt uploaded. - Salil
- Note from designer Elaine Park: This follows the suggestion showing both creativity and the appreciation of a good solution.
- Revised ppt uploaded. - Salil
- Note from designer Elaine Park: Put more emphasis on the text.
