= 27d567bc2d48d9f40e9ccc20ea370b15)
Kindly comments on Where Fermi Fails: What is hard to estimate? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (46)
Combinatorics is even better: you can state a problem in ten seconds with a numerical answer that would take years to compute with supercomputers. For instance, find the Ramsey number R(5,5). Wikipedia says it's (an integer) between 43 and 49.
At first this may seem unfair, but it's parallel to tan(10^100) in that there's only computation left to do; the computation in this case being to check all possible colorings of complete graphs with some number of vertices.
Also, isn't GCD a rather poor example, being the one number theoretic problem that does have an efficient algorithm to solve?
R(5, 5) is hard to solve exactly, but easy to estimate: 46 is correct to within 10%.
(Although perhaps only Feynman could produce such an estimate in ten seconds, without knowing the range beforehand.)
Hah! I was wondering if someone would notice that blunder of mine. Congratulations!
(Given sixty seconds, well... the easy upper bound on R(5,5) is 70, the easy upper bound on R(4,4) is 20, and R(4,4) is known to be 18, so I would have probably guessed around 60, which isn't in the 10% range no matter what the real value is. Possibly someone with a better intuition for these things would think of a more calibrated argument, though.)