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. W

**hat’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 n^{2}, rather than like 2^{n}. 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. **