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 A ≤_m B as meaning

• "A is no more difficult to solve than B," or

• "B is at least as difficult to solve as A."

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, X ≤_m 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.

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.

Proof. Suppose that A is m-complete. Then X ≤_m 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. ◊