Knowledge, Creativity and P vs NP – Wigderson

Source: IAS website, Apr 2009

we will explain the P versus NP question of computer science, and explain the consequences of its possible resolution, P = NP or P != NP, to the power and security of computing, the human quest for knowledge, and beyond. The connection rests on formalizing the role of creativity in the discovery process.

The seemingly abstract, philosophical question: Can creativity be automated? in its concrete, mathematical form: Does P = NP?, emerges as a central challenge of science. And the basic notions of space and time, studied as resources of efficient computation, emerge as key objects of study to solving this mystery, just like their physical counterparts hold the key to understanding the laws of nature.

P versus NP – can creativity be efficiently automated?

Let us write these definitions yet again:

  • P is the collection of all tasks for which a solution can be efficiently
  • NP is the collection of all tasks for which a solution, when given, can be
    efficiently verified.

It is evident that every problem in P is also in NP. The correctness of the algorithm generating the solution automatically certifies that solution!

But what about the converse?

Is it possible that for every problem for which verifying solution is easy, there is a simple program which would generate such valid solutions efficiently? This is the P = NP? question! To make formal sense, this question had to wait to the 1970s for the formal definitions of these classes in the above papers. It is remarkable, however, to note that the P = NP? question, in quite precise terms, appears already in 1954, in a letter from G¨odel to von Neumann (reproduced and translated in the survey [18]) which was discovered only in the 1990s.


The evidence against the mathematical form of P = NP will become clear when we discuss universality in the next section. The rest of this section is informal, and certainly specualtive.

Intuitively, most people revolt against the idea that such amazing discoveries like Wiles’ proof of Fermat, Einstein’s relativity, Darwin’s evolution, Edison’s inventions, as well as all the ones we are awaiting, could be produced in succession quickly by a mindless robot. We would similarly revolt against the possibility of a monkey spewing out a perfect Shakespeare tragedy.

And indeed, this analogy is in place. People have a strong sense that creativity was absolutely essential in these and other discoveries, and will be essential for important future ones. While elusive to define, people feel that creativity, ingenuity or leap-of-thought which lead to discoveries are the domain of very singular, talented and well-trained individuals, and that the process leading to discovery is anything but the churning of a prespecified procedure or recipe. These few stand in sharp contrast to the multitudes who can appreciate the discoveries after they are made.

So how can one explain the creativity which is demonstrated in the examples above, and elsewhere? Some thinkers develop theories whose foundation is a non computational model for cognitive functions. But all evidence shows that the brain, like every other natural process, is an efficient computational device4.

While science is extremely far from understanding the brain’s hardware and software, the laws of physics govern its behavior. And so if any problem was solved by any brain, it was (by definition) an efficiently solvable problem.  Clearly, some minds are stronger than others for performing different tasks. When others solve problems or make discoveries we feel we couldn’t have, we call them creative. But our concern here is with complete, universal creativity, rather than sporadic instances of it. We ask about the solvability of all tasks affording efficient recognition.

If P = NP, any human (or computer) would have the sort of reasoning power traditionally ascribed to deities, and this seems hard to accept. 


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s