# If two time complexity classes are equal what does that imply about the time complexity classes for corresponding proper complexity functions?

Say that two complexity classes are equal, i.e. TIME(n) = TIME(nlogn). Does this imply that for some proper complexity function f(n) >= n we can show TIME(f(n)) = TIME(f(n)(logf(n)))? If so, how can we strongly argue that they are equal and one is not just strictly contained in the other?

• Are you familiar with the technique of padding? Feb 24, 2022 at 19:05

Proving such theorems are usually done with the technique known as padding.

In your particular case, if we assume that "proper" funtions are functions we are used to (i.e, time constructible) then the statement is incorrect.

Let us assume this is note the case, and that the theorem is correct. Now, if $$f(n)$$ is some time-constructible function, then $$TIME(f(n))=TIME(f(n)\log(f(n)))$$.

Denote $$g(n):=f(n)\log(f(n))$$ and notice that $$g(n)$$ is a time-constructible function as well. Thus $$TIME(f(n))=TIME(g(n))=TIME(g(n)\log(g(n)))$$

But notice that $$h(n):=g(n)\log(g(n))=f(n)\log(f(n))\cdot \left( \log(f(n))+\log(\log(f(n)))\right)$$ is much larger than $$f(n)\log(f(n))$$ in the sense that $$f(n)\log(f(n))=o(h(n))$$.

Therefore, by the time heirarchy theorem, $$TIME(f(n))\subsetneq TIME(h(n))$$, but this contradicts our assumption that $$TIME(f(n))=TIME(g(n))=TIME(h(n))$$.

Thus we finally proved that this statement is incorrect. A similar proof may be utilized even if $$TIME(f(n))=TIME(f(n)\log^\epsilon (f(n))$$ for any $$\epsilon > 0$$.