3 ms·
"At the moment the most efficient algorithm (for integers larger than 100 digits) we can implement into pre-existing computers{3} has a sub-exponential running
by opportune 9y ago
"At the moment the most efficient algorithm (for integers larger than 100 digits) we can implement into pre-existing computers{3} has a sub-exponential running time. But we can’t say for certainty that the it is not in P."
Author needs to fix this typo. Additionally, I think this is sloppy reasoning and will confuse readers. Sub-exponential algorithms include polynomial algorithms, so saying that "X is subexponential but we can't prove it is not in P" is not as precise as "Algorithm X is subexponential but at best superpolynomial, which is not to say that problem Y cannot be in P in general".
- acchow 9y agoAgreed, the wording is a little strange but I think readers of this will understand the meaning anyway.
- schoen 9y agoIt's probably no less incorrect than saying "the suspect is now somewhere north of Mexico, but we haven't been able to rule out the possibility that he's in Canada" (with an unstated assumption that normally people said to be north of Mexico would be found in the United States). Edit: on reflection, I actually think I agree with opportune's concern after all, which I had slightly misunderstood at first.