Re:NP-Complete Problems and Physical Reality (2005)
by SilasX on Tuesday July 14, 2015 @02:32PM
(#9887050)
In terms of the computations performed in the brain by the mathematician, at the time the insight is achieved, it's not.
But appropriately accounted for, I think it is.
The relevant metric would be, "what do I have to increase in order to get more [interesting, new] theorems proved?" Is it as easy has having mathematicians work more hours? Having more people start working on them?
Intuitively, it is not so easy -- each insights need exponentially more work as time progresses. An exponentially-small fraction of humans is capable of producing novel results, and so on.
This, I think, is what Aaronson is getting at: if P = NP, if proving is as easy as verifying, then coming up with hard mathematical insights should be as easy as following a cookbook, or any other routine, mundane mental task.
But that doesn't seem to describe the world we live in, where getting mathematical insights has rapidly diminishing returns per unit resource invested.
But appropriately accounted for, I think it is.
The relevant metric would be, "what do I have to increase in order to get more [interesting, new] theorems proved?" Is it as easy has having mathematicians work more hours? Having more people start working on them?
Intuitively, it is not so easy -- each insights need exponentially more work as time progresses. An exponentially-small fraction of humans is capable of producing novel results, and so on.
This, I think, is what Aaronson is getting at: if P = NP, if proving is as easy as verifying, then coming up with hard mathematical insights should be as easy as following a cookbook, or any other routine, mundane mental task.
But that doesn't seem to describe the world we live in, where getting mathematical insights has rapidly diminishing returns per unit resource invested.