For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T13:41:39Z https://cs.stackexchange.com/feeds/question/1138 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/1138 18 For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? sepp2k https://cs.stackexchange.com/users/46 2012-04-08T19:06:59Z 2019-02-04T22:14:05Z <p>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?</p> <p>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:</p> <p>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:</p> <pre><code>x = f(n) for i from 1 to x: output(".") </code></pre> <p>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 functions<sup>1</sup>.</p> <p>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.</p> <hr> <p><sup>1</sup> Consider for example the function $p(n) = \cases{1 &amp; \text{if$n$is prime} \\ 2 &amp; \text{otherwise}}$. Clearly $O(p(n)) = O(1)$, but there is no algorithm that calculates $p$ in $O(1)$ time.</p> https://cs.stackexchange.com/questions/1138/-/1139#1139 12 Answer by Ran G. for For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? Ran G. https://cs.stackexchange.com/users/157 2012-04-08T19:49:23Z 2012-04-08T20:29:35Z <blockquote> <p>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?</p> </blockquote> <p>If $f$ is <a href="https://en.wikipedia.org/wiki/Constructible_function">a time-constructible function</a>, then the <a href="https://en.wikipedia.org/wiki/Time_hierarchy_theorem">Time Hierarchy Theorem</a> 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)$$</p> <p>This consider only decision problems, and does not regard the time it takes to generate the output.</p> https://cs.stackexchange.com/questions/1138/-/1140#1140 3 Answer by agorenst for For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? agorenst https://cs.stackexchange.com/users/871 2012-04-08T19:50:06Z 2019-02-04T22:14:05Z <p>I will try to provide something of a framework in the hopes it grants deeper insight.</p> <p>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.</p> <p>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.</p> <p>I don't think this will answer your question, but you may be interested in this: <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Time_hierarchy_theorem</a></p> <p>Also, be careful about the <a href="https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem" rel="nofollow noreferrer">speedup theorem</a>.</p> https://cs.stackexchange.com/questions/1138/-/1146#1146 12 Answer by Alex ten Brink for For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? Alex ten Brink https://cs.stackexchange.com/users/92 2012-04-08T23:14:55Z 2012-04-09T12:47:00Z <p>By the <a href="http://en.wikipedia.org/wiki/Gap_theorem">Gap theorem</a> (using the formulation from <a href="http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf">here</a>, 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))$.</p> <p>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.</p> <p>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).</p> <p>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 <em>does</em> mention and prove this (see <a href="http://ecommons.library.cornell.edu/handle/1813/5899">here</a>, for example).</p>