Category: Cryptocreativity

Knowledge, Creativity and P vs NP – Wigderson

Published on by ddcolrsLeave a comment

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

Automated Creativity & the P vs NP conjecture: Scott Aaronson

Published on by ddcolrsLeave a comment

Source: Scott Aaronson website, date indeterminate

One way to measure P vs. NP‘s importance is this. If NP problems were feasible, then mathematical creativity could be automated. 

Related Resource: Scientific American interview,

even those applications aren’t what personally interest me, as much as the way P vs. NP asks about the nature of mathematical creativity itself.

That’s the motivation Kurt Gödel offered in 1956, when he posed P vs. NP for possibly the first time, in a now-famous letter to John von Neumann.  As Gödel pointed out in his letter, if mathematical proofs are written in a sufficiently hairsplitting way (like in Russell and Whitehead’s Principia Mathematica), then it’s easy to write a fast computer program that checks, line-by-line, whether a given proof is valid.  That means there’s also a program to check whether a given statement has a proof that’s at most n symbols long: such a program just needs to try every possible combination of symbols, one after the next (like in Borges’ Library of Babel), and see whether any of them constitute a valid proof.  What’s not obvious is whether there’s a program to find a proof of length n, whenever one exists, using a number of steps that grows only like n or n2, rather than like 2n.  That question is essentially P vs. NP.

So if you found a fast computer program to find short proofs, then yes, that would solve one of the seven million-dollar prize problems.  But it would also solve the other six!  For it would mean that, if the Riemann Hypothesis, the Hodge Conjecture, and so forth had proofs of a reasonable length at all, then you could just program your computer to find those proofs for you.  The way Gödel put it was that, if P=NP in a practical way, then “the mental effort of the mathematician could be completely replaced by machines (apart from the postulation of axioms).”

Indeed, it’s easy to get carried away, and wax too poetic about the P vs. NP problem’s metaphysical enormity—as I’ve sometimes been accused of doing!  So let me be clear: P vs. NP is not asking whether the human mind can solve problems that digital computers can’t, which is the much more familiar question surrounding artificial intelligence.  Even if (as most of us think) P≠NP, that still might not prevent a Singularity or a robot uprising, since the robots wouldn’t need to solve all NP problems in polynomial time: they’d merely need to be smarter than us!  Conversely, if P=NP, that would mean that any kind of creative product your computer could efficiently recognize, it could also efficiently create.