We want to prove that boolean satisfiability is NP-complete. Suppose that T is an NTM, with input alphabet Sigma, w a string over Sigma, and N an integer. We will construct a boolean expression E = E[T,N,w] such that E is satisfiable if and only if T accepts w in at most N steps. The length of E will be a polynomial function of N, the length of w, and the length of the description of T. Furthermore, the construction of E takes only polynomial time in those same variables. Details of the construction will be given in class. We use this construction to prove that boolean satisfiability is NP-complete, as follows. Trivially, boolean satisfiability is NP. Suppose that L is any language in the class NP. Then there is an NTM T which accepts L, and a fixed number k, such that, for any string w in L of length n, T accepts w in at most 1 + n^k steps. For a given string w, we can reduce the problem of membership in L to boolean satisfiability, using the above construction. Let N = 1 + n^k, and construct the boolean expression E = E[T,N,w] as above. Then E is satisfiable if and only if w in L. Since the construction of E takes polynomial time, this is a polynomial time reduction of L to boolean satisfiability. This completes the proof that boolean satisfiability is NP-complete.