We now give a polynomial time rection of any NP language L
to Boolean satisfiability.

Let M be an NTM which accepts L is polynomial time.  We can assume that
there exist constants A, B, and k, such that, if w is in L, and w has
length n, there is a computation of M consisting of A + n^k steps, such
that each configuration has length at most A + Bn.

The reduction is as follows.  Suppose w is an input string.

	1.  Let n be the length of w.
	2.  Compute E = R(w,A+Bn,A+n^k).

It takes only polynomial time in n to compute E, and E is satisfiable
if and only if w is in L.

We conclude that Boolean satisfiability is NP-complete.