10.2. Properties of Polynomial-Time Reducibility

The fundamental theorem of polynomial time reducibility

---

Suppose that A and B are two languages.

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

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

for every string x.

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

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

Here is an algorithm to decide A in polynomial time.

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

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

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 n^k steps, f(x) does not have time to write more than n^k symbols. So u ≤ n^k.

Testing whether y ∈ B takes time no more than u^m. But that is no more than (n^k)^m, which is n^km.

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

Polynomial-time reducibility is transitive

---

The proof is left as an exercise.