
Suppose that A and B are two languages.
Theorem. If A ≤_{p} B and B ∈ P then A ∈ P.
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}. ◊
Theorem. If A ≤_{p} B and B ≤_{p} C then A ≤_{p} C.
The proof is left as an exercise.
