18
$\begingroup$

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

This question popped into my head yesterday. I've been thinking about it for a bit now, but can't figure it out. I don't really know how I'd google for this, so I'm asking here. Here's what I've come up with:

My first thought was that the answer is yes: For every computable function $f$ the problem "Output $f(n)$ dots" (or create a string with $f(n)$ dots or whatever) can obviously not be solved in $o(f(n))$ time. So we only need to show that it can be solved in $O(f(n))$ time. No problem, just take the following pseudo code:

x = f(n)
for i from 1 to x:
    output(".")

Clearly that algorithm solves the stated problem. And it's runtime is obviously in $\Theta(f(n))$, so problem solved. That was easy, right? Except no, it isn't because you have to consider the cost of the first line. The above algorithm's runtime is only in $\Theta(f(n))$ if the time needed to calculate $f(n)$ is in $O(f(n))$. Clearly that's not true for all functions1.

So this approach didn't get me anywhere. I'd be grateful for anyone pointing me in the right direction to figure this out properly.


1 Consider for example the function $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$. Clearly $O(p(n)) = O(1)$, but there is no algorithm that calculates $p$ in $O(1)$ time.

$\endgroup$
  • 1
    $\begingroup$ I don't think your two statements in your first paragraphs are necessarily each other's contrapositives: what if you have an $f$ such that there exists some problem that can be solved in $O(f(n))$, not in $o(f(n))$, nor in $\Theta(f(n))$ time? $\endgroup$ – Alex ten Brink Apr 8 '12 at 22:41
  • $\begingroup$ @Alex That's a good point I didn't consider that. $\endgroup$ – sepp2k Apr 9 '12 at 12:14
12
$\begingroup$

By the Gap theorem (using the formulation from here, search for 'gap'), for any computable unbounded function $g : \mathbb{N} \rightarrow \mathbb{N}$, there exists some increasing (in fact, arbitrarily large) computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $DTIME(f(n)) = DTIME(g(f(n))$.

This answers your question in that there exists such an $f$ (infinitely many, in fact): for every computable function $g$ such that $g = o(n)$, there exists some increasing function $f$ such that all problems solvable in $O(f(n))$ time are also solvable in $O(g(f(n)) = o(f(n))$ time. Note that $f$ is not necessarily time-constructible - for the time-constructible case, see the answer by @RanG.

In the Wikipedia formulation (which requires that $g(x) \geq x$), then $g \circ f$ becomes your example, and $f$ needs to be $\omega(n)$ (so you go the other way around - 'problems solvable in $O(g(f(n))$ are also solvable in $O(g(n))$' is the interesting part).

The Wikipedia article does not note that $f$ is increasing and can in fact be arbitrarily large ($f(n) \geq g(n)$ for instance). The article that proves the gap theorem does mention and prove this (see here, for example).

$\endgroup$
  • $\begingroup$ can $g$ be $o(n)$? Isn't it required that $g(x)\ge x$? Your statement is still correct, but the proof goes the other way, right? $\endgroup$ – Ran G. Apr 8 '12 at 23:33
  • $\begingroup$ @RanG. Updated to give a proof for both formulations (I used the formulation in the paper) :) $\endgroup$ – Alex ten Brink Apr 9 '12 at 0:09
  • $\begingroup$ "for every computable function g such that g=o(n), there exists some function f such that all problems solvable in O(f(n)) time are also solvable in O(g(f(n))=o(f(n)) time" What if all the fs that exist for that g are in O(1)? Then O(g(f(n)) is still O(1) and thus not o(1). $\endgroup$ – sepp2k Apr 9 '12 at 12:25
  • $\begingroup$ @sepp2k: good catch, this is indeed an issue as formulated. I've updated my answer. $\endgroup$ – Alex ten Brink Apr 9 '12 at 12:48
12
$\begingroup$

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

If $f$ is a time-constructible function, then the Time Hierarchy Theorem says that there are problems that require $O(f(n))$ time, and cannot be solved with time $o\left (\frac{f(n)}{\log(f(n))}\right )$. Specifically, $$ \text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$$

This consider only decision problems, and does not regard the time it takes to generate the output.

$\endgroup$
  • $\begingroup$ Am I right in assuming that if we consider non-time-constructible functions, the answer to my question is "no"? Or relatedly: if a function $f$ is not time-constructible and thus there is no Turing machine that halts after $f(n)$ steps, does that mean there is also no Turing machine that halts after $\Theta(f(n))$ steps? Because from that it would trivially follow that the answer to my question is no. $\endgroup$ – sepp2k Apr 8 '12 at 20:12
  • $\begingroup$ It depends. Assume $f$ is not time-constructible but can be bounded by some other function $g$ which is time-constructible. $f=\Theta(g)$ and there still exists problems which can be solved with time $O(f)$ but not too much less than that. $\endgroup$ – Ran G. Apr 8 '12 at 20:16
  • $\begingroup$ and using multiple tape TMs, you can improve the result from $o(\frac{f(n)}{\lg f(n)})$ to $o(f(n))$. $\endgroup$ – Kaveh Apr 9 '12 at 2:48
3
$\begingroup$

I will try to provide something of a framework in the hopes it grants deeper insight.

When you get to something this fundamental there are unexpected pitfalls everywhere. For example: what is it to "solve" a problem? Often in computer science we consider only the "decision" variant, in which we are given an input and need only to output True or False. You are focusing on the "function" problem.

If you consider O(f(n)) notation as trying to capture how much "work" is needed to solve a problem, using decision instead of function (where output is required) seems better because you cleanly separate the computation from the output formatting.

I don't think this will answer your question, but you may be interested in this: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Also, be careful about the speedup theorem.

$\endgroup$

Your Answer

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

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