17.10. Complete and Hard Problems

Complete problems

---

Let C be a class of problems and let ≤ be one of the kinds of reducibilities, such as ≤_m or ≤_p.

Problem A is complete for C with respect to reducibility ≤ provided both of the following are true.

1. A ∈ C.

2. For every X ∈ C, X ≤ A.

We use completeness when C has a subclass D, and where the reducibility ≤ is conservative for class D.

Then, suppose that problem A is complete for C with respect to ≤, and that D ⊂ C. From that, we can show what A ∉ D, as follows.

1. Select a problem X that is in C but not in D.

2. We know that X ≤ A, since A is complete for C.

3. Because X ≤ A, we know that

   X ∉ D ⇒ A ∉ D.

4. But we selected X so that X ∉ D. So A ∉ D.

Some kinds of completeness

---

• An m-complete problem is complete for the partially computable problems with respect to ≤_m. Every m-complete problem is uncomputable, because

  1. ≤_m is conservative for the class of computable problems.
  2. There exists a partially computable problem that is not computable. (The Halting Problem, for example.)

  The Halting Problem is an example of an m-complete problem.

• An NP-complete problem is complete for NP with respect to ≤_p.

  We have part of what is needed: ≤_p is conservative for P. But we do not know that P ⊂ NP. That is just a conjecture.

  We know that, if P ≠ NP, then no NP-complete problem can be in P.

  We have seen examples of NP-complete problems, including 3-SAT, Vertex Cover and the Subset Sum problem.

• A PSPACE-complete problem is complete for PSPACE with respect to ≤_p.

  ≤_p is conservative for NP. So, if NP ⊂ PSPACE, then no PSPACE-complete problem can be in NP.

  We have seen examples of PSPACE-complete problems, including TQBF and Generalized Geography.

• An EXPTIME-complete problem is complete for EXPTIME with respect to ≤_p.

Problems that are hard for a class

---

Problem A is hard for class C with respect to reducibility relation ≤ if

The difference between completeness and hardness is that a hard problem for class C is not necessarily in class C.

Usually, we use Turing reducibility for hardness. NP-hard, PSPACE-hard and EXPTIME-hard are all defined with respect to ≤_p^t.

For example, the following problem is NP-hard.

Input. A list of positive integers x₁, x₂, …, x_k.

Output An index set I ⊆ {1, …, k } so that

is as small as possible.

That problem cannot be in NP because it is not a decision problem. But it is easy to show that the Partition Problem reduces to it by a polynomial-time Turing reduction. (Try it.)

You should be prepared to show that a particular problem is NP-complete or CoNP-complete or PSPACE-complete. You should also be prepared to show that a given problem is NP-hard.