20
$\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$
2
  • 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$ Apr 8, 2012 at 22:41
  • $\begingroup$ @Alex That's a good point I didn't consider that. $\endgroup$
    – sepp2k
    Apr 9, 2012 at 12:14

3 Answers 3

14
$\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$
5
  • $\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, 2012 at 23:33
  • $\begingroup$ @RanG. Updated to give a proof for both formulations (I used the formulation in the paper) :) $\endgroup$ Apr 9, 2012 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, 2012 at 12:25
  • $\begingroup$ @sepp2k: good catch, this is indeed an issue as formulated. I've updated my answer. $\endgroup$ Apr 9, 2012 at 12:48
  • $\begingroup$ @AlextenBrink The second link doesn't work, can you update it? $\endgroup$
    – user777
    Apr 3, 2021 at 17:14
14
$\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$
3
  • $\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, 2012 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, 2012 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, 2012 at 2:48
4
$\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$
0

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.