Timeline for Approximate number of primes below a given integer?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2013 at 21:34 | comment | added | Mark Lewko | @Dror, I agree that that is likely what Alex meant. I didn't mean to suggest that this was a complete solution, only partial progress. | |
| Apr 8, 2013 at 13:55 | comment | added | Joël | but the formula of Hardy, Ramanujan and Rademacher allows for an exact computation in polynomial time. | |
| Apr 8, 2013 at 13:53 | comment | added | Joël | So we have subexponential time algorithm, but nothing close to a polynomial time. Is it expected that there is no polynomial time algorithm, or on the contrary that there is some method ? Or perhaps people disagree about what to expect, as I have read somewhere on this site, they disagree if we ought to expect that the factorization problem can be solved in polynomial time or not. An indication that there might be a positive answer is an analogy with an admittedly rather different case, the one of the partition function $p(n)$. Computing it naively is certainly exponential time (or more)... | |
| Apr 8, 2013 at 7:57 | comment | added | Dror Speiser | I'm guessing the words "polynomial time" above are meant in the logarithm of $n$. To answer that, it would be interesting to know how well the Lagarias-Odlyzko algorithm approximates $\pi(x)$ if one is only willing to put it in $log^k(x)$ time. | |
| Apr 8, 2013 at 6:50 | history | answered | Mark Lewko | CC BY-SA 3.0 |