> "People think that P≠NP, because they tried it hard, and did not find any NP-hard problem in P."
That was the informal explanation given to the computer scientists. But that's not so convincing to non computer scientists and it's not the informal 'pop science' explanation.
An example (not the only one) of the kind of 'pop science' explanation I mean, is Impagliazzo's Five Worlds (https://gwern.net/doc/cs/cryptography/1995-impagliazzo.pdf). One of those hypothetical worlds he called 'Algorithmica' and it's where P = NP. One of the amazing and outlandish things that could be accomplished in such an exotic world would be the following feat: "Thus, a computer could be taught to recognize and parse grammatically correct English just by having sufficiently many examples of correct and incorrect English statements, without needing any specialized knowledge of grammar or English."
It's not so wild to me, to think that if someone's understanding of P vs. NP was from that kind of pop science article, then they would think we should start considering more seriously that we are in the Algorithmica (P = NP) world where such feats are possible!
If P = NP because there's a O(N^{Graham's Number}) polynomial algorithm - a 'galactic algorithm' indeed - then the lay description is theoretically correct, but meaningless in practice.
In particular, the hand-waving is the phrase 'sufficiently many examples.' This may be impossible to provide even if only a googol (10^100) examples are needed, because of mass and energy limitations of the universe - there's only so much you can do with 10^80 atoms, and the speed of light is too slow.
The Wikipedia entry for "galactic algorithm" at https://en.wikipedia.org/wiki/Galactic_algorithm even mentions SAT: "a hypothetical large but polynomial O(n^2^100) algorithm for the Boolean satisfiability problem, although unusable in practice, would settle the P versus NP problem".
Algorithmica may therefore be very little different than our world, other than that people no longer debate if P = NP.
Thank you. I stand corrected, people indeed argued "10-15 years ago, the basic idea was "P≠NP because otherwise computers could do crazy shit." (1 person at least).
Informal, as in, poorly-researched clickbait pop-science. Most of the serious pop-science sources (Scientific American, Quanta Magazine, Computerphile, etc.) have explained it correctly, without restoring to woo.
