I find this thought funny: The faster the reduction, the stronger the lower bound. When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to yo

I find this thought funny: The faster the reduction, the stronger the lower bound. When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. However, when you speed up the reduction to linear time, your lower bound is quadratic time! This also applies to simulations of TMs. The faster the simulation, the sharper the complexity classes. Thus, by making something faster, you can show that something else cannot be made faster anymore. (Afaik this also applies to P vs NP: Find a fast enough algorithm to reduce an arbitrary problem in EXP to NP and you showed that P!=NP)