Reputation: 1
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