3 ms·
I think your evaluation of the post may have been somewhat rushed. - The poster is a notable complexity theorist and is not "just trying to get attention". -
by anatoly 17y ago
I think your evaluation of the post may have been somewhat rushed.
- The poster is a notable complexity theorist and is not "just trying to get attention".
- Doron Zeilberger's "a lot more interesting" take is completely subsumed in Richard Lipton's blogpost, in that it mentions other possibilities beyond the basic "what if it's polynomial with a really huge exponent" scenario.
- Assuming computational power to increase exponentially indefinitely is completely ridiculous, and without the "indefinitely" part this assumption no longer works to justify "easy = P".
- It is trivial to say that if P=NP, then AM=MA, because both AM and MA are in the polynomial hierarchy, and if P=NP, the hierarchy collapses completely.
- The most important point to be taken away from the blogpost is not just that "easy = P" is an assumption that's been held on too unreflectively and may not turn out to be true. It's that studying what this assumption means, how it could break down, and why it hasn't, by and large, broken down so far, may get us closer to understanding P ?= NP.
- alextp 17y agoYou have a point. My closeted complexity theorist persona thinks it would be a lot more interesting to study the special cases of P (not just LOG, but seeing how O(n) and O(n²) or "NO(n)" problems behave) instead of the most general cases.