12
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 9
    $\begingroup$ 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. $\endgroup$
    – cody
    Feb 11, 2012 at 21:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – Alex ten Brink
    Feb 12, 2012 at 0:21
  • 8
    $\begingroup$ @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. $\endgroup$
    – Jukka Suomela
    Feb 12, 2012 at 2:24
  • 8
    $\begingroup$ 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". $\endgroup$
    – Jeffε
    Feb 12, 2012 at 14:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 13, 2012 at 2:33

5 Answers 5

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Feb 16, 2012 at 22:45
  • 2
    $\begingroup$ It’s quite tangential to your point, but: minor-closed graph properties can be in fact decided in time $O(n^2)$ research.nii.ac.jp/~k_keniti/quaddp1.pdf . $\endgroup$
    – Emil Jeřábek
    Feb 17, 2012 at 12:56
  • 1
    $\begingroup$ @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: arxiv.org/abs/1109.5036 $\endgroup$
    – András Salamon
    Feb 17, 2012 at 14:23
  • 1
    $\begingroup$ By the way, Kowarabayashi and Wollan claim a bound on the constant in their STOC 2011 paper 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. $\endgroup$
    – András Salamon
    Feb 17, 2012 at 14:52
  • 2
    $\begingroup$ 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 : fi.muni.cz/~hlineny/papers/plcover20-gc.pdf $\endgroup$
    – Denis
    Feb 17, 2017 at 14:21
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why P has a very large complexity? $\endgroup$
    – user35592
    Feb 17, 2017 at 15:09
  • $\begingroup$ Because the speed up process can be iterated, hence it must be compatible with an infinite chain of algorithms of decreasing complexity. $\endgroup$
    – Andrea Asperti
    Feb 17, 2017 at 15:42
3
$\begingroup$

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

Improve this answer
$\endgroup$
-4
$\begingroup$

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" 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 is total recursive but not primitive recursive 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 or paris-harrington thms

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ not an answer to the question. $\endgroup$
    – Kaveh
    Feb 13, 2012 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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