Arthur J. O'Dwyer wrote: > >  - I'm fairly sure there exist classes of problems with no "best" > solution, but merely an infinite family of solutions each of which is > better than the last. I don't have any examples, but I'd be interested > to see one.
You are probably referring to Blum's speedup theorem from 1967: "http://en.wikipedia.org/wiki/Blum%27s_speedup_theorem", "http://mathworld.wolfram.com/BlumsSpeed-UpTheorem.html"?
Another result of the same type is the theorem in "http://locus.siam.org/SICOMP/volume-15/art_0215027.html", which roughly speaking states that if P != NP, then any algorithm A for any "natural" NP-complete problem X can be "speeded up to a polynomial" on infinitely many new inputs, in the sense that there is another algorithm A' that runs in polynomial time on the same inputs as A, and then some.
-- Pekka Orponen Helsinki University of Technology