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.
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.