0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Are you familiar with the technique of padding? $\endgroup$ Feb 24, 2022 at 19:05

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.