Automatic Complexity

5 The incompressibility theorem

Shallit and Wang showed that the automatic complexity A(x) satisfies A(x)n/13 for almost all x{0,1}n. They also stated that Holger Petersen had informed them that the constant 13 can be reduced to 7. Here we show that it can be reduced to 2+ϵ for any ϵ>0. The result also applies to nondeterministic automatic complexity AN(x). In that setting the result is tight inasmuch as AN(x)n/2+1 for all x.