Let me offer a real life example where a version of this heuristic seems valid: Fermat claimed to have a proof of what is now called Fermat’s Last Theorem (that the equation x^n + y^n =z^n has no solutions in positive integers with n>2). This was finally proven in the mid 90s by Andrew Wiles using very sophisticated techniques. Now, in the 150 or so year period where this problem was a famous unsolved problem, many people, both professional mathematicians and amateurs tried to find a proof. There are still amateurs trying to find a proof that is simpler than Wiles, and ideally find a proof that could have been constructed by Fermat given the techniques he had access to. There’s probably no theorem that has had more erroneous proofs presented for it, and likely no other theorem that has had more cranks insist they have a proof even when the flaws are pointed out (cranks are like that). If some new individual shows up saying they have a simple, elementary proof of Fermat’s Last Theorem, it is reasonable to assign this claim a very low confidence because someone would have noticed it by now. Since so many people (many of whom are very smart) have been expressly looking for such a proof for a very long time, we can be pretty sure that if such a simple proof existed it would have been found by now.
The “somebody would have noticed’” heuristic thus functions like many other heuristics. In some cases the heuristic will fail. And the heuristic will likely fail more frequently in situations like Wednesday where the individual is either ignorant or surrounded by people who make basic mistakes in rationality. But properly used, the heuristic can still be useful and reliable.
Except this is an attitude that discourages people from working on a lot of problems and occasionally its proven wrong.
You could often here computer scientists being sloppy about the whole Prime Factorization is NP-hard argument with statements like “If NP is not equal to P one can’t determine if a number is prime or not in polynomial time.” And stuff like this is probably one of the more famous examples of things people are discouraged from working on based on “Somebody would have noticed by now”.
Guess what, this was shown to be doable, and it shocked people when it came out.
A few problems with that. First of all, anyone actually paying attention enough to think about the problem of determining primality in polynomial time thought that it was doable. Before Agrawal’s work, there were multiple algorithms believed but not proven to run in polynomial time. Both the elliptic curve method and the deterministic Miller-Rabin test were thought to run in polynomial time (and the second can be shown to run in polynomial time assuming some widely believed properties about the zeros of certain L-functions). What was shocking was how simple Agrawal et al.’s algorithm was. But even then, far fewer people were working on this problem than people who worked on proving FLT. And although Agrawal’s algorithm was comparatively simple, the proof that it ran in P-time required deep results.
Second, even factoring is not believed to be NP-hard. More likely, factoring lies in NP but is not NP-hard. Factoring being NP-hard with P != NP would lead to strange stuff including partial collapse of the complexity hierarchy (Edit: to be more explicit it would imply that NP= co-NP. The claim that P != NP but NP = co-NP would be extremely weird.) I’m not aware of any computer scientist who would be so sloppy as to make the statements you assert are often heard.
Overall, Agrawal doesn’t compare well to the use of the heuristic here because Agrawal’s method (a generalized version of Euler’s congruence for polynomials) was an original method.
That said, I agree that such a heuristic can lead people seriously astray if it is applied too often. As with any heuristic it can be wrong. Using any single heuristic by itself is rarely a good approach.
Often was a stretch and much of the factual information is a little off.
I guess my experience taking lower level complexity courses with people who don’t do theory means what I often hear are statements by people who consider themselves computer scientist that you think no computer scientist would make.
I upvoted your post because I’m glad for the correction and read up about the problem after you made it.
Let me offer a real life example where a version of this heuristic seems valid: Fermat claimed to have a proof of what is now called Fermat’s Last Theorem (that the equation x^n + y^n =z^n has no solutions in positive integers with n>2). This was finally proven in the mid 90s by Andrew Wiles using very sophisticated techniques. Now, in the 150 or so year period where this problem was a famous unsolved problem, many people, both professional mathematicians and amateurs tried to find a proof. There are still amateurs trying to find a proof that is simpler than Wiles, and ideally find a proof that could have been constructed by Fermat given the techniques he had access to. There’s probably no theorem that has had more erroneous proofs presented for it, and likely no other theorem that has had more cranks insist they have a proof even when the flaws are pointed out (cranks are like that). If some new individual shows up saying they have a simple, elementary proof of Fermat’s Last Theorem, it is reasonable to assign this claim a very low confidence because someone would have noticed it by now. Since so many people (many of whom are very smart) have been expressly looking for such a proof for a very long time, we can be pretty sure that if such a simple proof existed it would have been found by now.
The “somebody would have noticed’” heuristic thus functions like many other heuristics. In some cases the heuristic will fail. And the heuristic will likely fail more frequently in situations like Wednesday where the individual is either ignorant or surrounded by people who make basic mistakes in rationality. But properly used, the heuristic can still be useful and reliable.
Except this is an attitude that discourages people from working on a lot of problems and occasionally its proven wrong.
You could often here computer scientists being sloppy about the whole Prime Factorization is NP-hard argument with statements like “If NP is not equal to P one can’t determine if a number is prime or not in polynomial time.” And stuff like this is probably one of the more famous examples of things people are discouraged from working on based on “Somebody would have noticed by now”.
Guess what, this was shown to be doable, and it shocked people when it came out.
A few problems with that. First of all, anyone actually paying attention enough to think about the problem of determining primality in polynomial time thought that it was doable. Before Agrawal’s work, there were multiple algorithms believed but not proven to run in polynomial time. Both the elliptic curve method and the deterministic Miller-Rabin test were thought to run in polynomial time (and the second can be shown to run in polynomial time assuming some widely believed properties about the zeros of certain L-functions). What was shocking was how simple Agrawal et al.’s algorithm was. But even then, far fewer people were working on this problem than people who worked on proving FLT. And although Agrawal’s algorithm was comparatively simple, the proof that it ran in P-time required deep results.
Second, even factoring is not believed to be NP-hard. More likely, factoring lies in NP but is not NP-hard. Factoring being NP-hard with P != NP would lead to strange stuff including partial collapse of the complexity hierarchy (Edit: to be more explicit it would imply that NP= co-NP. The claim that P != NP but NP = co-NP would be extremely weird.) I’m not aware of any computer scientist who would be so sloppy as to make the statements you assert are often heard.
Overall, Agrawal doesn’t compare well to the use of the heuristic here because Agrawal’s method (a generalized version of Euler’s congruence for polynomials) was an original method.
That said, I agree that such a heuristic can lead people seriously astray if it is applied too often. As with any heuristic it can be wrong. Using any single heuristic by itself is rarely a good approach.
Agree, my previous post was very sloppy.
Often was a stretch and much of the factual information is a little off.
I guess my experience taking lower level complexity courses with people who don’t do theory means what I often hear are statements by people who consider themselves computer scientist that you think no computer scientist would make.
I upvoted your post because I’m glad for the correction and read up about the problem after you made it.