## Regarding the number of asymptotically optimal algorithms

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

### Regarding the number of asymptotically optimal algorithms

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.
JTHM

Posts: 16
Joined: Sun Apr 22, 2012 4:29 am UTC

### Re: Regarding the number of asymptotically optimal algorithm

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))),...
jareds

Posts: 357
Joined: Wed Jan 03, 2007 3:56 pm UTC

### Re: Regarding the number of asymptotically optimal algorithm

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?
JTHM

Posts: 16
Joined: Sun Apr 22, 2012 4:29 am UTC

### Re: Regarding the number of asymptotically optimal algorithm

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.
letterX

Posts: 511
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: Regarding the number of asymptotically optimal algorithm

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1553
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Who is online

Users browsing this forum: No registered users and 3 guests