Regarding the number of asymptotically optimal algorithms

[JTHM]

Does anyone know of a proof that there exist an infinite number of distinct (non-mutually-reducible) problems for which there are asymptotically optimal algorithms that decide them?

I apologize if this is a dumb question, but I'm not a CS major.

[jareds]

I am not 100% sure what you're asking, but the following statement may be along the lines of what you're looking for.

By the time hierarchy theorem, it is straightforward to construct an infinite number of distinct complexity classes with distinct worst-case bounds on running time. For example, DTIME(2^n), DTIME(2^(2^n)), DTIME(2^(2^(2^n))),...

[JTHM]

Ah, that would do it... But is there a proof that all of those classes are non-empty? That is, that for every class in the hierarchy, there exists some problem which belongs to it, and to no easier class?

[letterX]

Yes. That's exactly what the Time Heirarchy theorem says. Note the little subset-not-equal to relation on the wiki page two posts ago.

[WarDaft]

We can not only show that there are an infinite number of not-mutually-reducible problems with asymptotically optimal solutions, but that there are an infinite number of distinct asymptotically optimal solutions.

Consider a Gödel Machine given the PA axioms. This machine is, by definition, asymptotically optimal for any problem with a solution that can be expressed and proven optimal within PA.

Courtesy of Gödel's incompleteness theorems, we know there are problems outside any given consistent axiomatic system which contains, for example, PA. That means that for any Gödel Machine armed with PA+X for any PA consistent axioms X, there is another Gödel Machine, distinct from the first, with axioms PA+X+Con(PA+X). This can prove things distinctly beyond that which can be proven by the first, and so will have a wider range of problems for which it is asymptotically optimal. The easiest of these to see is proving things about what the first machine can actually eventually solve. This is something that the first machine is not only not optimal for, but cannot even do.

Now, we can ask if this is really a class of distinct solutions, we can say "mightn't we construct a Gödel Machine that takes as input, in addition to the problems it solves, a list of axioms it should assume?" Yes, we could do this, which might seem to make the entire above hierarchy collapse into a single solution, but we must remember the UTM. The UTM can solve any problem given the right algorithm as additional input, but that does not mean that all problems are solved by the UTM, merely that all solutions can be executed on it.