Are we there yet?

Question: Alice decides to visit her good friend Bob. How much time will it take her to get there?

Alas, in life, as in mathematics, we do not always know everything, and predicting exactly how much time it will take Alice to get to Bob can be a hard task. But we can try to give bounds on how large can be.

Answer 1: All we know is that Alice and Bob are two different entities somewhere in the universe. So

Very basic, very true, but frankly, a bit uninformative.

Answer 2: We know that nothing travels faster than light, which goes at speed in vacuum. If the distance between Alice and Bob is , then

Hey, it’s better than nothing. For example, if Alice lives in central Rehovot and Bob lives in central Tel-Aviv, then they live about 19,600 meters apart, and it would take Alice at least 0.0000653 seconds to get to Bob.

Answer 3: Everything in life is somewhere else, and you get there using a car; Alice makes no exception. Being a model citizen, she drives on roads; she actually has to plot a course using a map, and decide which streets to take. Alice observes the rules of traffic and does not drive more than the speed limit, and so we can split her journey into parts: if the speed limit on street number is , and the street is meters long, then

This bound is already useful (not least beacuse we don’t use the speed of light anymore). It’s already close to how a person might estimate arrival time in real-life (e.g. divide the trip into “freeway” and “urban” sections). If Alice goes according to the route in the image below, she’ll have to drive about 27.4 kilometers. Sticking to the 90 km/h speed limit, it would take her at least twenty minutes to get to Bob. This is already a fair estimate.

Answer 4: Alice can take both historical and real-time data consisting of congestion, car accidents, pedestrian density, construction sites, traffic signs, traffic-light-synchronization, Jupiter’s exaltation, and her own personal driving habits, and throw it into a multi-armed-bandit algorithm, also known as GoogleMaps or Waze. After many clever computations, she gets both a proposed course, and an estimated time for how much time it will take her to get to Bob. She’d be pretty hard pressed to give a general expression for ; certainly it won’t be as simple as the ones above. But it will probably be quite accurate.

The most useful bound yet, in terms of prediction power. But it is very, very complicated, mashing together intricate knowledge about the driver, the roads, other drivers, and the local siesta. Here, like many Israelis, Alice would be stuck in traffic.

---

I see these four answers as different stages of mathematical understanding and problem solving. When faced with a new problem, we usually try to get the obvious out of the way (Answer 1). Then, a small insight can often give us something better (Answer 2). With more effort, and more knowledge about the problem, we can get a fairly accurate answer (Answer 3). Finally, if we really want exact bounds, we’re going to have to put in a lot of effort to understand how minute details interact with each other (Answer 4). Doing this might require heavy machinery, or it might even be infeasible with current technology.

Not all problems follow this description, but a good example which does is the computational cost of matrix multiplication. Given two matrices and , how many operations do we need in order to compute the product ? The definition of matrix multiplication gives an algorithm with operations (Answer 1). A simple trick can give something better, on the order of (Answer 2). Current state-of-the-art results use much more refined techniques to arrive at operations (Answer 3). Many people think that the best algorithm needs only slightly more than operations (this is the best lower bound we have). Who knows? Answer 4 hasn’t been given yet.

(Although Answer 1 and Answer 2 seem laughably weak, sometimes they are the best we got. This often happens when the problems are really, really hard (e.g. the entire field of computational complexity theory)).