gomultimajor
gomultimajor

Reputation: 1

For any two time constructable function, will there exist a time construtcable function between it in big-O notation?

In other words, is the family of time-constructable function 'dense', as the set of rational numbers are?

The reason why I thought of this is that, there are infinitely many time constructable function between n and n^2. Since family of n(log n)^k are all time-constructable. (my proof: given n as a binary representation, computing log n (as a expression of binary integer) takes O(n) time, and multiplying binary representation takes log n so we can compute n(logn)^k in n(logn)^k for any k, and we can just write that amount of 1s in the tape)

actually for any time-constructable function f we can do simillarly and construct f(n)(logf(n))^k so for any f(n) and f(n)^2, there are infinitely many time constructable function between them... can we do this for any other tighter gaps then f and f^2, or even arbitrary gaps, like f and flogf, too?

I tried methods using f*log(f/g) which is absolutely between f and g, but this requires to compute g in f*log(f/g) which makes general way to construct a function below g really hard.

Upvotes: 0

Views: 24

Answers (0)

Related Questions