Timeline for Examples of notably long or difficult proofs that only improve upon existing results by a small amount
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2019 at 15:45 | comment | added | Zach Teitler | This was the subject of an SMBC (Saturday Morning Breakfast Cereal) webcomic: smbc-comics.com/comic/mathematicians | |
| Jan 18, 2019 at 2:30 | comment | added | Solveit | @TomChurch How do we know $O(n^2)$ is impossible? | |
| Sep 27, 2018 at 6:09 | comment | added | Tom Church | $O(n^2)$ is impossible; the conjecture is $O(n^{2+\varepsilon})$. But by the same token the proofs here do not actually prove e.g. $O(n^{2.374})$, but rather $O(n^{2.374+\varepsilon})$. | |
| Sep 11, 2018 at 11:14 | comment | added | Simd | @FedericoPoloni $O(n^2 \log{n})$ is certainly in $O(n^{2+\epsilon})$ for $\epsilon > 0$ but $O(n^{2+\epsilon})$ is not in $O(n^2 \log{n})$. The question is whether $O(n^2 \log{n})$ would also be shocking. | |
| Sep 9, 2018 at 10:08 | comment | added | Federico Poloni | @Mitch A function in $O(n^2\log n)$ is also in $O(n^{2+\epsilon})$ for any $\epsilon>0$; that is just a more general form that includes essentially all "$n^2$ times logarithmic factors" classes. | |
| Sep 9, 2018 at 0:26 | comment | added | Mitch | @StevenStadnicki, Christopher: Isn't $O(n^2 \log(n))$ a viable conjecture? | |
| Sep 6, 2018 at 17:11 | comment | added | Steven Stadnicki | @Christopher $O(n^2)$ I think would be a shock, but $O(n^{2+\epsilon})$ for any $\epsilon$ is a lot more plausible. | |
| Sep 6, 2018 at 15:59 | history | made wiki | Post Made Community Wiki by S. Carnahan♦ | ||
| Sep 6, 2018 at 10:36 | comment | added | Christopher | It's probably worth pointing out that [according to the papers, I don't know the subject myself] the strong-but-widely-believed conjecture - analogous to the Riemann hypothesis in the example in the question - is that the asymptotic complexity is $O(n^2)$. | |
| Sep 6, 2018 at 9:02 | history | edited | Federico Poloni | CC BY-SA 4.0 |
added 8 characters in body
|
| Sep 6, 2018 at 8:55 | history | edited | Federico Poloni | CC BY-SA 4.0 |
deleted 6 characters in body
|
| Sep 6, 2018 at 8:50 | history | answered | Federico Poloni | CC BY-SA 4.0 |