1
$\begingroup$

We know that there are languages in $DTIME(n^t)$ and not in $DTIME(n^s)$ for all $t>s$ due to simple diagonal arguments (i.e., the Time Hierarchy Theorem), but I'm wondering if there is any equivalent results known for time-bounded Kolmogorov complexity. That is, given polynomials $p(n)=n^t$ and $q(n)=n^s$ with $t>s$ is it always true that for any sufficiently large length $k$ there exists a string $x$, $|x|=k$ such that $C^p(x)<C^q(x)$? If this is not true, is it true for ${CD}^p(x)<{CD}^q(x)$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.