Timeline for $\mathbf{P} = \mathbf{NP}$, what's the problem?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2022 at 15:18 | comment | added | Dattier | @Steven We can calculate $\cos(2^{2000})$ with $100$ digits. | |
| Apr 14, 2022 at 13:33 | history | edited | user21820 | CC BY-SA 4.0 |
edited title
|
| S Apr 13, 2022 at 17:56 | history | suggested | CommunityBot | CC BY-SA 4.0 |
Using "..." instead of \cdots causes a conspicuous asymmetry. \mod instead of \bmod puts too much white space to its left, inappropriate in this context. And other copy-editing.
|
| Apr 13, 2022 at 17:48 | review | Suggested edits | |||
| S Apr 13, 2022 at 17:56 | |||||
| Apr 13, 2022 at 17:12 | comment | added | gnasher729 | Anyone here with a copy of Mathematica who can create a graph for the function, say if Ak = nth prime. and V is half their total size, rounded to an even integer? I suspect you run into trouble for relatively small an, while solving it for say n = 1,000,000 is no big deal with a pseudo-polynomial algorithm. | |
| Apr 13, 2022 at 17:06 | answer | added | gnasher729 | timeline score: 21 | |
| Apr 13, 2022 at 7:21 | comment | added | Dan Romik | @StevenStadnicki okay, I suppose that's true. In that case I'll revise the point that I was trying to make earlier about bottlenecks: the point is that even if we were allowed to use an oracle that computes $\pi$ at any desired precision for zero computational cost, it likely wouldn't be of much help in computing the integral in polynomial time. (Not that I have an idea how to prove such a statement; I'm just speaking heuristically here.) So in that sense, I'm guessing that $\pi$ is not the bottleneck. | |
| Apr 13, 2022 at 6:17 | history | became hot network question | |||
| Apr 13, 2022 at 1:41 | comment | added | Steven Stadnicki | @DanRomik That depends entirely on how many digits we need. Since as Noam Elkies's answer notes we have waves of frequency $A_i=\theta(2^n)$, then to compute $A_it\bmod \pi$ we still need (as far as we know) $\theta(2^n)$ digits — i.e. exponentially many. | |
| Apr 13, 2022 at 1:37 | comment | added | Dan Romik | @StevenStadnicki true, but the computation of pi isn’t going to be the bottleneck here, see for example this paper. (Related discussion here.) | |
| Apr 13, 2022 at 1:31 | comment | added | Steven Stadnicki | 'We know excellent approximation[s] of $\pi$' doesn't matter in the asymptotic limit; we can't assume that we have 'all of' $\pi$ written down in advance so computing it has to be part of the calculation as well. | |
| Apr 12, 2022 at 22:44 | answer | added | Noam D. Elkies | timeline score: 51 | |
| Apr 12, 2022 at 22:22 | history | edited | Dattier | CC BY-SA 4.0 |
added 4 characters in body
|
| Apr 12, 2022 at 22:17 | history | asked | Dattier | CC BY-SA 4.0 |