4 ms·

> "10-15 years ago, the basic idea was "P≠NP because otherwise computers could do crazy shit." Everyone is downvoting you because that's not the mathematical e

by ftxbro 3y ago

> "10-15 years ago, the basic idea was "P≠NP because otherwise computers could do crazy shit." Everyone is downvoting you because that's not the mathematical explanation, but it's absolutely the informal explanation that the 'pop science' ones were saying.

bmacho 3y ago
I don't think it was the informal explanation ever. People think that P≠NP, because they tried it hard, and did not find any NP-hard problem in P.
- ftxbro 3y ago
  > "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 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!
  - eesmith 3y ago
    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. "Only a googol" because Graham's Number is mind-boggingly huge - https://en.wikipedia.org/wiki/Graham%27s_number https://en.wikipedia.org/wiki/Graham%27s_number The Wikipedia entry for "galactic algorithm" at https://en.wikipedia.org/wiki/Galactic_algorithm 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.
  - bmacho 3y ago
    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).
- creatonez 3y ago
  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.
ComplexSystems 3y ago
I don't mind the downvotes as I expected this would be somewhat provocative, going against the general grain that people think P≠NP. I agree that, in general, this is not a mathematical explanation for why P≠NP, but a rough heuristic to explain why people think it is true, predominantly in pop sci circles. I would also emphasize that there is no mathematical explanation for P≠NP - or else the problem would be solved - and at the end of the day, the reasons that computer scientists suspect this to be true are equally heuristic in nature, not amounting to much more than "we tried to solve these problems and couldn't do it."

by ftxbro 3y ago

bmacho 3y ago

I don't think it was the informal explanation ever. People think that P≠NP, because they tried it hard, and did not find any NP-hard problem in P.

ftxbro 3y ago
> "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 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!
- eesmith 3y ago
  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. "Only a googol" because Graham's Number is mind-boggingly huge - https://en.wikipedia.org/wiki/Graham%27s_number https://en.wikipedia.org/wiki/Graham%27s_number The Wikipedia entry for "galactic algorithm" at https://en.wikipedia.org/wiki/Galactic_algorithm 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.
- bmacho 3y ago
  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).
creatonez 3y ago
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.

ComplexSystems 3y ago

I don't mind the downvotes as I expected this would be somewhat provocative, going against the general grain that people think P≠NP. I agree that, in general, this is not a mathematical explanation for why P≠NP, but a rough heuristic to explain why people think it is true, predominantly in pop sci circles. I would also emphasize that there is no mathematical explanation for P≠NP - or else the problem would be solved - and at the end of the day, the reasons that computer scientists suspect this to be true are equally heuristic in nature, not amounting to much more than "we tried to solve these problems and couldn't do it."