Re:My survey article on P vs. NP (2017)
by SilasX on Tuesday March 23, 2021 @10:43AM
(#26555639)
I think Aaronson addresses that in 1.2.6 as the "obviousness objection", "a proof of P ̸= NP—confirming that indeed, we can’t do something that no reasonable person would ever have imagined we could do—gives almost no useful information."
To which he replies,
>>to make a sweeping statement like P ̸= NP, about what polynomial-time algorithms can't do, will require an unprecedented understanding of what they can do. This will almost certainly entail the discovery of many new polynomial-time algorithms, some of which could have practical relevance. In Section 6, we’ll see much more subtle examples of the “duality” between algorithms and impossibility proofs, with progress on each informing the other.
To which he replies,
>>to make a sweeping statement like P ̸= NP, about what polynomial-time algorithms can't do, will require an unprecedented understanding of what they can do. This will almost certainly entail the discovery of many new polynomial-time algorithms, some of which could have practical relevance. In Section 6, we’ll see much more subtle examples of the “duality” between algorithms and impossibility proofs, with progress on each informing the other.