Complexity theory’s 50-year journey to the limits of knowledge
This is an aside. But I twigged on a caption for one of the figures: “Every computational problem takes longer to solve as its input grows larger, but not all problems grow harder at the same rate.”<p>It’s obvious from CS201 that this phrase is generally true and I have no pedantic objection to its inclusion in the article. However, I’m curious if this is strictly true or if we can find a (nontrivial) counterexample. Are there any algorithms that run faster as input grows? My first intuition is some kind of probabilistic question solved to a given correctness bound.<p>Edit: it is trivial to construct an algorithm with this property. My precise question is whether any meaningful problems have optimal algorithms with this property.