1
$\begingroup$

In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned that any unsolvable problem would have a complexity of infinite.

However, this strikes me as strange. It feels intuitive to me to say that an unsolvable problem would have no complexity, as any attempt to solve it would be impossible. The quantity of infinity says to me that "if you had unlimited time, you could solve it", but what if it's a question that the answer simply cannot be computed for?

Is this O(infinity) concept common in algorithmic complexity analyses?

$\endgroup$
  • $\begingroup$ ""if you had unlimited time, you could solve it", but what if it's a question that the answer simply cannot be computed for?" I don't understand what it means to be able to solve something in infinite time - assuming by "unlimited" you mean "infinite". When do you decide that you're done? If your answer to this is "after infinite time", then you'll have to provide some formalization for this, because this is usually hand-waving that doesn't make any sense - similar to saying "I've got a number, and in the decimal representation of my number, there are infinitely many zeroes and then a $1$". $\endgroup$ – G. Bach Apr 27 '16 at 11:12
2
$\begingroup$

Basically, this is a degenerate case. We can adopt the convention that the running time of any algorithm is $\infty$ (so its complexity is $\infty$), or we can adopt the convention that it doesn't have a complexity. For informal conversation, probably it doesn't matter much what convention you adopt, as long as it's clear which you're using and what you mean.

See also how to calculate time complexity of non terminating loops for discussion of the running time of an algorithm that never terminates, and What is the difference between an algorithm, a language and a problem? for background on the difference between the complexity of an algorithm vs the complexity of a problem.

$\endgroup$
2
$\begingroup$

Your instructor is right, and this seems like an odd choice.

$O(\infty)$ arises usually as a way to say "this algorithm may never terminate, it's awful, let's never use it."

Big-O and Running Time

First, what about big-O complexity of your problem? Well, problems don't have big-O complexity, algorithms do. So if there is no algorithm to solve your problem, then we can't talk about how many steps it takes an algorithm to solve your problem.

Complexity Classes, P, NP, etc.

But, what about complexity classes, NP-hard, etc?

The main classes are restricted to decidable problems. For example, $NP$ is the class of problems solveable by a Turing Machine running in non-deterministic polynomial time. But this is a subset of the class of solveable problems. Similar statements can be made about $P$, $EXP$, $PSPACE$, etc.

What about "hardness?" Can an undecidable problem be $NP$-hard? Yes, but not in an interesting way.

Informally, to show that a problem is $NP$-hard, we assume that we have an algorithm solving it, and we show that we can then solve another $NP$-hard problem in polynomial time with a polynomial number of calls to our algorithm.

But in your case, to do so is to assume that there is an algorithm solving an unsolveable problem. This means we've assumed a contradiction, so we can derive a polynomial time algorithm for some NP-hard problem, since we can derive literally anything from the contradiction. We've assumed False, and this provides us with no useful information.

Summing Up

The idea of standard complexity isn't even well-defined for an undecidable problem.

You problem will be in basically no complexity classes, but it will be Hard for almost every complexity class.

$\endgroup$
  • $\begingroup$ This is very interesting. Particularly, my problem is computing the Kolmogorov complexity of a string. As you know, there is no function to compute this given arbitrary x. So, as stated, the problem is unsolvable. According to what you say here, since there cannot exist an algorithm to solve this, we should not have an analysis, which I fully agree with. But I think this is the kind of teacher that epitomizes "I am right and you are wrong", so I'm almost afraid to not give an analysis. Thank you for your food for thought. $\endgroup$ – Bronze Apr 27 '16 at 2:12
  • $\begingroup$ @user327716 Okay, but the teacher is right and you are wrong. You should probably choose a different problem, since there's not much analysis to give. $\endgroup$ – jmite Apr 27 '16 at 2:25
  • $\begingroup$ I can't tell whether to feel insulted or commiserated with. I'm aware that he is right, I was speaking generally that in most cases he is unwilling to cooperate or discuss. In other words, he is the smartest person he knows. $\endgroup$ – Bronze Apr 27 '16 at 2:28
  • 1
    $\begingroup$ @user327716 fair enough, and I can't comment too much on the social aspect. I'm just trying to reiterate that it's probably not wise to try to knock your teacher down a peg by providing an analysis, if there is no analysis you can provide. $\endgroup$ – jmite Apr 27 '16 at 2:29
  • $\begingroup$ Parts of this answer replicate our reference question. $\endgroup$ – Raphael Apr 27 '16 at 9:42
2
$\begingroup$

Do you want to talk algorithm analysis or complexity theory?

Algorithms

Every algorithm has running time in $O(\infty)$ since that, by definition, means

$\qquad \exists\, c, n_0.\ \forall\, n \geq n_0.\ T(n) \leq c \cdot \infty$,

assuming a reasonable extension of $\leq$ to $\mathbb{R} \cup \{\infty\}$.

Every algorithm that always terminates has running time not in $\Theta(\infty)$; if one extends the definitions carefully enough, they have running time in $o(\infty)$.

Algorithms that do not terminate (sometimes) do not solve any problem (in a strict sense).

Problems

The time "complexity" of a problem $P$ is the $\Theta$-class of the running time of a $\Theta$-time-optimal algorithm for $P$.

There are no algorithms for undecidable problems, so they do not have a complexity.

If you want to start thinking about what is possible with infinitely many monkeys, you should be aware that there are degrees of uncomputability; see the arithmetical hierarchy.

$\endgroup$
1
$\begingroup$

When dealing with undecidable problem, the correct way of classifying problems is recursion theory rather than complexity theory. For example, whereas a hard computable problem might be, say, NP-complete, a hard uncomputable problem might be $\Sigma_1^0$-complete.

NP is just the first rung on the polynomial hierarchy, and is also known by the name $\Sigma_1^P$. The recursion-theoretic analog (which of course predates the polynomial hierarchy) is the arithmetical hierarchy, of which $\Sigma_1^0$ (which corresponds to the halting problem) is the first rung.

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