<p>For every algorithm $A$ that terminates on a class of inputs $\mathsf{In}$, we can <em>define</em> the function of its running times:
$$
f(n)=\max_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),
$$
where $\mathsf{In}(n)$ is the class of inputs of length $n$ and $\mathsf{time}(A(i))$ is the time algorithm $A$ requires to terminate on $i$. Of course, this definition is unsatisfying as it relates to the algorithm, but it shows the existence of such a function. 
The question that remains is whether there exists a <em>concise</em> representation (and I believe that this was what you were asking for).</p>

<p>If we use simple algebraic terms (without recursion of any sort) as definition of concise, then I think the answer is no: There are problems which can be decided but whose complexity is nonelementary. That is, there does not exist a stack of the form $2^{2^{2^{2^{\dots^n}}}}$ that bounds the execution time of an algorithm for a problem of size n. </p>

<p>I hope I understood your question in the right way.</p>

CC BY-SA 3.0
2012-02-12T12:35:03.533Z
2012-02-12T12:35:03.533Z
Markus
<p>This is a slightly different take on your question than Marcus's, but in light of your explanation of how you came to think of this question, it may be closer to what you are looking for.</p>

<p>Sometimes one can prove that a problem is decidable, without being able to exhibit the algorithm for it.  The most famous example of this sort of thing is the work of Robertson and Seymour on graph minors, which shows that any hereditary graph property can be decided in polynomial time, by checking for the presence of a suitable finite list of forbidden minors.  Their proof shows only that a finite list of forbidden minors exists, but does not provide a recipe for <i>finding</i> the list.</p>

<p>I'm not an expert in the area so I don't know offhand of a specific example of a hereditary graph property for which we cannot exhibit an algorithm because we do not know the list of forbidden minors and we know of no other way to solve the problem, but I suspect that such examples exist.  (And we can bound the running time for finding an example if it exists, since we know that there are at most 8 billion people in the world and in the worst case we could ask them all!)</p>

<p>One further remark: Since we know that checking for a minor can be done in $O(n^3)$ time, you could argue that in all the cases furnished by the Robertson&ndash;Seymour algorithm, we <i>do</i> have a "bound" of $O(n^3)$ on the running time.  However, I would argue that this is sort of cheating, if we have no bound on the constant.</p>

CC BY-SA 3.0
2012-02-16T19:03:26.403Z
For specific examples where we don't have a better algorithm, pick any finite set of excluded minors that has not yet been studied.  There are lots of these.  :-)
András Salamon
CC BY-SA 3.0
2012-02-16T22:45:35.183Z
But if you pick an explicit set of excluded minors, then you can exhibit an algorithm.  Better would be to pick some hereditary property that hasn't been studied.  This is a bit trickier to do, though.
Timothy Chow
CC BY-SA 3.0
2012-02-17T12:56:21.837Z
It’s quite tangential to your point, but: minor-closed graph properties can be in fact decided in time $O(n^2)$ http://research.nii.ac.jp/~k_keniti/quaddp1.pdf .
Emil Jeřábek
CC BY-SA 3.0
2012-02-17T14:23:48.060Z
@EmilJeřábek: even more tangentially, deciding if a graph from a minor-closed family satisfies a first-order property can be done in linear time: http://arxiv.org/abs/1109.5036
András Salamon
CC BY-SA 3.0
2012-02-17T14:52:04.737Z
By the way, Kowarabayashi and Wollan claim a bound on the constant in their STOC 2011 paper http://www.dsi.uniroma1.it/~wollan/PUBS/shorter_struct_web.pdf which also reports on further progress that is "not yet fully written down".  However, I cannot easily extract an explicit bound from this paper.
András Salamon
CC BY-SA 3.0
2017-02-17T14:21:55.393Z
For such an example, you have graphs with a planar cover. Weirdly, we almost know a list: there are 31 forbidden minors, and a 32nd potential one, but for this last one it is open whether it has a planar cover or not. Therefore we don't have an algorithm for this class of graphs. See for instance : https://www.fi.muni.cz/~hlineny/papers/plcover20-gc.pdf
Denis
CC BY-SA 3.0
2012-02-16T16:02:05.683Z
2012-02-16T16:02:05.683Z
Timothy Chow
<p>Just to add a different perspective, let me recall that not every problem has an "intrinsic" complexity, that is probably the most interesting and somehow neglected consequence of Blum's speedup theorem.</p>

<p>Essentially the theorem states that, fixed a desired speedup g, you may always find a computational problem P such that for <em>any</em> program solving P there exists another program still solving P and running g-times faster than the previous one. </p>

<p>Hence, for this kind of problems you cannot give a time bound.
Amazing, and quite puzzling result. Of course P has a very large complexity.</p>

CC BY-SA 3.0
2017-02-17T15:42:07.077Z
Because the speed up process can be iterated, hence it must be compatible with an infinite chain of algorithms of decreasing complexity.
Andrea Asperti
CC BY-SA 3.0
2017-02-17T11:07:40.347Z
2017-02-17T11:07:40.347Z
Andrea Asperti
<p>The theoretical aspect of your question is taken care of by Markus.
More practically, an interesting way to understand your question is: are there decidable problems for which we don't know of any time bound ?</p>

<p>The answer is yes: for instance it can happen that you have a semi-algorithm for YES instances of your problem, and a semi-algorithm for NO instances. This gives you decidability of your problem, but no time bound.</p>

<p>Here is a generic example: assume you have an axiomatic system allowing you to prove all true identities in some algebra. Moreover, you know that false identities are always witnessed by a finite structure.</p>

<p>Then you have the following algorithm to decide whether an identity $I$ is true: enumerate in parallel proofs and finite structures, and stop when you find a proof of $I$ or a structure witnessing that $I$ is false. It gives you a correct algorithm but no complexity bound, unless you can bound the size of proofs and finite structures with respect to $I$.</p>

<p>An example of this is affine linear logic (LLW): it is now known to be Tower-complete [1], but for some time no bounds were known, and only decidability was shown, using among other techniques finite model property [2].</p>

<p><strong>References:</strong></p>

<p>[1] <em>Non-elementary complexities for branching VASS, MELL, and extensions.</em>
Ranko Lazic and Sylvain Schmitz. CSL-LICS 2014</p>

<p>[2] <em>The finite model property for various fragments of linear logic.</em>
Yves Lafont, J. Symb. Logic. 1997</p>

CC BY-SA 3.0
2017-02-17T12:44:24.620Z
2017-02-17T14:11:24.820Z
2017-02-17T14:11:24.820Z
Denis
<p>as others have stated the question is not stated in a way that avoids a trivial answer however there are some concepts in TCS &amp; number theory that are related/similar.</p>

<p>1) in the space and time hierarchy theorems the concept of <a href="http://en.wikipedia.org/wiki/Space_constructible" rel="nofollow">"time constructible" and "space constructible"</a> functions are required. non time constructible and non space constructible functions exist and lead to unusual properties found in the Blum theorems such as the "gap, speedup" theorems. most (all?) std complexity classes are defined in terms of space and time constructible functions.</p>

<p>2) the <a href="http://en.wikipedia.org/wiki/Ackermann_function" rel="nofollow">ackerman function</a> is total recursive but not <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function" rel="nofollow">primitive recursive</a> and this has implications for its time bound. the primitive recursive functions in some sense represent the "basic" mathematical operations.</p>

<p>3) there are thms about number theory sequences uncomputable in peano arithmetic that can be interpreted as creating not-computable-in-a-sense time bounds such as the <a href="http://en.wikipedia.org/wiki/Goodstein%27s_theorem" rel="nofollow">goodstein sequence</a> or 
<a href="http://en.wikipedia.org/wiki/Paris-Harrington_theorem" rel="nofollow">paris-harrington</a> thms</p>

CC BY-SA 3.0
2012-02-13T00:48:06.603Z
not an answer to the question.
Kaveh
CC BY-SA 3.0
2012-02-12T16:58:57.190Z
2012-02-12T17:08:26.977Z
2012-02-12T17:08:26.977Z
vzn
<p>Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?</p>

<p>I arrived at this question because I was thinking about the following:</p>

<p>Assume we
have a recursively enumerable, but undecidable problem. Assume further that I is
a "yes"-instance of the problem. Then for no algorithm which identifies the
"yes"-instances of the problem we can give a time bound in terms of the size n
of I. For if we could give such a time bound, we could decide the problem, as we
could simply conclude that I is a "no"-instance when the time bound is exceeded.</p>

<p>Since we cannot give a time bound for recursively enumerable, undecidable
problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we
cannot give a time bound.</p>

CC BY-SA 3.0
2012-02-11T21:43:09.503Z
There is a trivial time bound on such algorithms: run the algorithm, and return the number of steps performed by that algorithm. On the other hand it is easy to construct examples for which it is difficult to give bounds that are easy to understand or express, e.g. the ackermann function.
cody
CC BY-SA 3.0
2012-02-12T00:09:51.913Z
What I mean are not time bounds for a specific instance, but a time bound as a function of the size of an instance, e.g. n^2. My question is whether there are decision problems for which we cannot find such a function f(n), i.e. there are always instances for which the runtime exceeds f(n), for any f.
Hermann
CC BY-SA 3.0
2012-02-12T00:21:37.623Z
You'll have to be more precise. If you talk about (mathematical) functions, then yes, there is a function matching the running time of any Turing machine (in fact, there are more functions than Turing machines). If you talk about computable functions or, equivalently, algorithms, then @cody gives you the answer: just run the Turing machine deciding the problem and count its running time.
Alex ten Brink
CC BY-SA 3.0
2012-02-12T02:24:17.043Z
@AlextenBrink: Actually, to get the *worst-case* running time as a function of input size $n$, you need to run the Turing machine for *all* possible inputs of size $n$, and take the maximum. But of course this is also doable.
Jukka Suomela
CC BY-SA 3.0
2012-02-12T14:03:51.507Z
As others say, the question as is stated is trivial.  For related notions, please check [elementary recursive functions](http://en.wikipedia.org/wiki/ELEMENTARY) and [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive_function).
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-12T14:05:54.963Z
May I suggest a revision?  To avoid the trivial answer, suppose we define the phrase "we can give a time bound" to mean "we can compute an upper bound on the worst-case running time _more quickly than by running the algorithm on all instances of size n."_  Or maybe "all instances" should be "a single instance".
Jeffε
CC BY-SA 3.0
2012-02-13T02:33:40.380Z
Your argument depends on your time bound function being *total* computable. It is well-known that this cannot be done, but if that is your question (i.e. there are partial computable functions with no total computable function extension) then the question is not research-level. Please see the [FAQ] for suggestions about where you might be able to ask this kind of questions.
Kaveh
<computability><time-complexity>
Are there decidable problems for which for no algorithm we can give time bounds?
Hermann
# Are there decidable problems for which for no algorithm we can give time bounds?

(Asked by: username_0 on 2012-02-11)

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?

I arrived at this question because I was thinking about the following:

Assume we
have a recursively enumerable, but undecidable problem. Assume further that I is
a "yes"-instance of the problem. Then for no algorithm which identifies the
"yes"-instances of the problem we can give a time bound in terms of the size n
of I. For if we could give such a time bound, we could decide the problem, as we
could simply conclude that I is a "no"-instance when the time bound is exceeded.

Since we cannot give a time bound for recursively enumerable, undecidable
problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we
cannot give a time bound.

**Tags:** computability, time-complexity
> **Comments:**
> **username_1**: There is a trivial time bound on such algorithms: run the algorithm, and return the number of steps performed by that algorithm. On the other hand it is easy to construct examples for which it is difficult to give bounds that are easy to understand or express, e.g. the ackermann function.  
> **username_0**: What I mean are not time bounds for a specific instance, but a time bound as a function of the size of an instance, e.g. n^2. My question is whether there are decision problems for which we cannot find such a function f(n), i.e. there are always instances for which the runtime exceeds f(n), for any f.  
> **username_2**: You'll have to be more precise. If you talk about (mathematical) functions, then yes, there is a function matching the running time of any Turing machine (in fact, there are more functions than Turing machines). If you talk about computable functions or, equivalently, algorithms, then @cody gives you the answer: just run the Turing machine deciding the problem and count its running time.  
> **username_3**: @AlextenBrink: Actually, to get the *worst-case* running time as a function of input size $n$, you need to run the Turing machine for *all* possible inputs of size $n$, and take the maximum. But of course this is also doable.  
> **username_4**: As others say, the question as is stated is trivial.  For related notions, please check [elementary recursive functions](http://en.wikipedia.org/wiki/ELEMENTARY) and [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive_function).  
> **username_5**: May I suggest a revision?  To avoid the trivial answer, suppose we define the phrase "we can give a time bound" to mean "we can compute an upper bound on the worst-case running time _more quickly than by running the algorithm on all instances of size n."_  Or maybe "all instances" should be "a single instance".  
> **username_6**: Your argument depends on your time bound function being *total* computable. It is well-known that this cannot be done, but if that is your question (i.e. there are partial computable functions with no total computable function extension) then the question is not research-level. Please see the [FAQ] for suggestions about where you might be able to ask this kind of questions.  

---

## 5 answers

### Answer by username_7 on 2012-02-12. Score: 13

For every algorithm $A$ that terminates on a class of inputs $\mathsf{In}$, we can *define* the function of its running times:
$$
f(n)=\max\_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),
$$
where $\mathsf{In}(n)$ is the class of inputs of length $n$ and $\mathsf{time}(A(i))$ is the time algorithm $A$ requires to terminate on $i$. Of course, this definition is unsatisfying as it relates to the algorithm, but it shows the existence of such a function.
The question that remains is whether there exists a *concise* representation (and I believe that this was what you were asking for).

If we use simple algebraic terms (without recursion of any sort) as definition of concise, then I think the answer is no: There are problems which can be decided but whose complexity is nonelementary. That is, there does not exist a stack of the form $2^{2^{2^{2^{\dots^n}}}}$ that bounds the execution time of an algorithm for a problem of size n.

I hope I understood your question in the right way.


---

### Answer by username_8 on 2012-02-16. Score: 6

This is a slightly different take on your question than Marcus's, but in light of your explanation of how you came to think of this question, it may be closer to what you are looking for.

Sometimes one can prove that a problem is decidable, without being able to exhibit the algorithm for it. The most famous example of this sort of thing is the work of Robertson and Seymour on graph minors, which shows that any hereditary graph property can be decided in polynomial time, by checking for the presence of a suitable finite list of forbidden minors. Their proof shows only that a finite list of forbidden minors exists, but does not provide a recipe for *finding* the list.

I'm not an expert in the area so I don't know offhand of a specific example of a hereditary graph property for which we cannot exhibit an algorithm because we do not know the list of forbidden minors and we know of no other way to solve the problem, but I suspect that such examples exist. (And we can bound the running time for finding an example if it exists, since we know that there are at most 8 billion people in the world and in the worst case we could ask them all!)

One further remark: Since we know that checking for a minor can be done in $O(n^3)$ time, you could argue that in all the cases furnished by the Robertson–Seymour algorithm, we *do* have a "bound" of $O(n^3)$ on the running time. However, I would argue that this is sort of cheating, if we have no bound on the constant.

> **Comments:**
> **username_9**: For specific examples where we don't have a better algorithm, pick any finite set of excluded minors that has not yet been studied.  There are lots of these.  :-)  
> **username_8**: But if you pick an explicit set of excluded minors, then you can exhibit an algorithm.  Better would be to pick some hereditary property that hasn't been studied.  This is a bit trickier to do, though.  
> **username_10**: It’s quite tangential to your point, but: minor-closed graph properties can be in fact decided in time $O(n^2)$ http://research.nii.ac.jp/~k_keniti/quaddp1.pdf .  
> **username_9**: @EmilJeřábek: even more tangentially, deciding if a graph from a minor-closed family satisfies a first-order property can be done in linear time: http://arxiv.org/abs/1109.5036  
> **username_9**: By the way, Kowarabayashi and Wollan claim a bound on the constant in their STOC 2011 paper http://www.dsi.uniroma1.it/~wollan/PUBS/shorter_struct_web.pdf which also reports on further progress that is "not yet fully written down".  However, I cannot easily extract an explicit bound from this paper.  
> **username_11**: For such an example, you have graphs with a planar cover. Weirdly, we almost know a list: there are 31 forbidden minors, and a 32nd potential one, but for this last one it is open whether it has a planar cover or not. Therefore we don't have an algorithm for this class of graphs. See for instance : https://www.fi.muni.cz/~hlineny/papers/plcover20-gc.pdf  

---

### Answer by username_12 on 2017-02-17. Score: 3

Just to add a different perspective, let me recall that not every problem has an "intrinsic" complexity, that is probably the most interesting and somehow neglected consequence of Blum's speedup theorem.

Essentially the theorem states that, fixed a desired speedup g, you may always find a computational problem P such that for *any* program solving P there exists another program still solving P and running g-times faster than the previous one.

Hence, for this kind of problems you cannot give a time bound.
Amazing, and quite puzzling result. Of course P has a very large complexity.

> **Comments:**
> **username_12**: Because the speed up process can be iterated, hence it must be compatible with an infinite chain of algorithms of decreasing complexity.  

---

### Answer by username_11 on 2017-02-17. Score: 3

The theoretical aspect of your question is taken care of by Markus.
More practically, an interesting way to understand your question is: are there decidable problems for which we don't know of any time bound ?

The answer is yes: for instance it can happen that you have a semi-algorithm for YES instances of your problem, and a semi-algorithm for NO instances. This gives you decidability of your problem, but no time bound.

Here is a generic example: assume you have an axiomatic system allowing you to prove all true identities in some algebra. Moreover, you know that false identities are always witnessed by a finite structure.

Then you have the following algorithm to decide whether an identity $I$ is true: enumerate in parallel proofs and finite structures, and stop when you find a proof of $I$ or a structure witnessing that $I$ is false. It gives you a correct algorithm but no complexity bound, unless you can bound the size of proofs and finite structures with respect to $I$.

An example of this is affine linear logic (LLW): it is now known to be Tower-complete [1], but for some time no bounds were known, and only decidability was shown, using among other techniques finite model property [2].

**References:**

[1] *Non-elementary complexities for branching VASS, MELL, and extensions.*
Ranko Lazic and Sylvain Schmitz. CSL-LICS 2014

[2] *The finite model property for various fragments of linear logic.*
Yves Lafont, J. Symb. Logic. 1997


---

### Answer by username_13 on 2012-02-12. Score: -4

as others have stated the question is not stated in a way that avoids a trivial answer however there are some concepts in TCS & number theory that are related/similar.

1) in the space and time hierarchy theorems the concept of ["time constructible" and "space constructible"](http://en.wikipedia.org/wiki/Space_constructible) functions are required. non time constructible and non space constructible functions exist and lead to unusual properties found in the Blum theorems such as the "gap, speedup" theorems. most (all?) std complexity classes are defined in terms of space and time constructible functions.

2) the [ackerman function](http://en.wikipedia.org/wiki/Ackermann_function) is total recursive but not [primitive recursive](http://en.wikipedia.org/wiki/Primitive_recursive_function) and this has implications for its time bound. the primitive recursive functions in some sense represent the "basic" mathematical operations.

3) there are thms about number theory sequences uncomputable in peano arithmetic that can be interpreted as creating not-computable-in-a-sense time bounds such as the [goodstein sequence](http://en.wikipedia.org/wiki/Goodstein%27s_theorem) or
[paris-harrington](http://en.wikipedia.org/wiki/Paris-Harrington_theorem) thms

> **Comments:**
> **username_6**: not an answer to the question.  

---

