10.2. Properties of Polynomial-Time Reducibility

The fundamental theorem of polynomial time reducibility

Suppose that A and B are two languages.

Theorem. If Ap B and B ∈ P then A ∈ P.

Proof. Suppose that B ∈ P and Ap B. We need to show that A ∈ P.

Since Ap B, there is a function f that can be computed in polynomial time so that

xA ⇔ f(x) ∈ B

for every string x.

Since f can be computed in polynomial time, it must run in time at most nk for some k.

Since B ∈ P, there must be an algorithm to decide membership in B that runs in time nm for some m.

Here is an algorithm to decide A in polynomial time.

  inA(x):  // Return true if xA and false if xA.
  y = f(x)
  if y ∈ B then
    answer true
    answer false
  end if

Let n be the length of x. The first step, y = f(x), takes time no more than nk.

We need to know how long y can be. Let u be the length of y. Since computation of f(x) takes no more than nk steps, f(x) does not have time to write more than nk symbols. So unk.

Testing whether yB takes time no more than um. But that is no more than (nk)m, which is nkm.

So the entire algorithm for A runs in polynomial time in n, with polynomial nkm. ◊

Polynomial-time reducibility is transitive

Theorem. If Ap B and Bp C then Ap C.

The proof is left as an exercise.