Automated Creativity & the P vs NP conjecture: Scott Aaronson

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.  


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