Complexity analysis of an unsolvable algorithmic problem?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.