Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$). If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \mathrm{CTIME}(f(n))$, then, by a standard padding argument [KV87], for any $h(n)$ such that $h^c(n) = \Omega(f(n))$ with some constant $c$,

\begin{align*} \mathrm{CTIME}(n) \supseteq \mathrm{CTIME}(h(n)) &\implies \mathrm{CTIME}(h^i(n)) \supseteq \mathrm{CTIME}(h^{i+1}(n)) \\ & \implies \mathrm{CTIME}(n) \supseteq \mathrm{CTIME}(f(n)). \end{align*} Therefore $\mathrm{CTIME}(n) \subsetneq \mathrm{CTIME}(h(n))$. As an example, authors in [KV87] show that $\mathrm{BPTIME}(n^{\log n}) \subsetneq \mathrm{BPTIME}(2^{n^\epsilon})$ from $\mathrm{BPTIME}(n) \subsetneq \mathrm{BPTIME}(2^{O(n)})$.

Can we further improve this result as follows? (My intuition is NO but I don't know why. Maybe it has something to do with whether we can well order all probable "nice" functions, by defining $\textrm{"}f \leq g\textrm{"}\ :=\ \textrm{"}f=O(g)\textrm{"}$.)

We only need $h$ to satisfy that the union of "intervals" $$ [\Omega(t(n)), O(h(t(n))] $$ over all time-constructable $t(n)$ "covers" [$\Omega(n), O(f(n))$].

Suppose, throughout this process, we only consider "nice" function constructed by recursively applying arithmetic operation, $2^x$ or $\log x$ (e.g. $n^{\log n/\log \log n}$).


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.