4
$\begingroup$

Consider the following algorithm that computes the sum of two integers (toy example):

INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!

$\endgroup$
  • $\begingroup$ You are really asking about the Halting Problem. Turing said that given a program that there is no computational way to determine whether or not the program will eventually halt, or run forever. Do just a bit of google searching and you will find information about this. $\endgroup$ – SDsolar Jan 3 '17 at 12:27
5
$\begingroup$

The textbook Computational Complexity: A Modern Approach by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class cannot capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.

$\endgroup$
  • $\begingroup$ Statistics has no problem defining expected values for probability distributions that are not limited. $\endgroup$ – gnasher729 Jan 3 '17 at 12:40
  • $\begingroup$ @gnasher729 And that can be great fun! For example, how much would you pay to enter a casino with a game in which each round, you flip a coin. If it lands tails, the game ends, but if it lands heads, you get a dollar and get to play again, but each next time, you get double the amount of the previous game. Personally, I wouldn't pay a great amount to play this game, even though the expected return of this game is infinite. The point I was trying to make is that, even in spite of available mathematical tools, this concept isn't studied bcos doesn't look very useful in the context of algorithms. $\endgroup$ – Lieuwe Vinkhuijzen Jan 3 '17 at 13:37
2
$\begingroup$

I doubt this idea has been studied because, to me, it doesn't seem at all useful. The only thing that would allow you to use your example algorithm is the fact that you have an exact running time bound on the terminating option, which means that you can detect that you were in the non-halting case, abort and restart. In general, of course, you can't detect that you're in a non-halting case, so you can't use this trick. Also, the trick relies on the algorithm being probabilistic. In a deterministic algorithm, even if you could detect the infinite loop, you'd only be able to return "I don't know", which isn't a correct answer to whatever problem you're trying to solve.

The closest concept I'm aware of is Las Vegas algorithms. These are randomized algorithms that always produce the correct answer on termination, and that terminate in expected finite time. Indeed, the abort-and-restart version of your example algorithm is an example of a Las Vegas algorithm – in expectation, you need one abort (assuming the coin is unbiased).

$\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.