8.1. M-Complete Problems

This will be our last topic on computability before beginning complexity theory. The ideas explored here will feed directly into complexity.

An analogy

Suppose that you have a room of people, and you want to find the tallest person in the room. Putting aside how you would accomplish that, let's give a definition of the tallest person in the room.

An individual I is a tallest person in the room if both of the following are true.

  1. I is in the room.

  2. For every individual X who is in the room, I is at least as tall as X.

Note that this definition allows for the possibility that two individuals are equally tall.

Applying the analogy to computational problems

Suppose that A and B are two languages.

If you think in rough, intuitive terms, you can think of Am B as meaning

That is, you think of ≤m as meaning "less than or equal to in difficulty."

If you have a class C of problems then, following the previous analogy, you might say that I is a hardest problem in class C if both of the following are true.

  1. I is in class C.

  2. For every problem X in class C, Xm I.

Definition of complete problems

In fact, we are going to use just that idea where C is the class of partially computable languages.

Suppose that A is a language.

Definition. Language A is m-complete if both of the following are true.

  1. A is partially computable.

  2. For every partially computable language X, Xm A.

Intuitively, an m-complete language is one of the hardest partially computable languages to solve. As such, you would not expect it to be computable.

After all, some partially computable languages are uncomputable, and those are surely harder to solve than any computable languages.

It turns out that intuition is correct, but we need to demonstrate that it is.

Theorem. If language A is m-complete, then A is not computable.

Proof. Suppose that A is m-complete. Then Xm A for every partially computable language X.

Since HALT is partially computable, it must be the case that HALT ≤m A.

But HALT is uncomputable. By the fundamental theorem of mapping reducibility, A is also uncomputable. ◊