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?
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.)
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.)