sec hard problems satisfiability (satinputa boolean expression over variables in conjunctive normal form outputyes if there is an assignment to the variables that makes trueno otherwise cook proved that sat is -hard explaining this proof is beyond the scope of this book but we can briefly summarize it as follows any decision problem can be recast as some language acceptance problem lf (iyes ( accept that isif decision problem yields yes on input ithen there is language containing string where is some suitable transformation of input converselyif would give answer no for input ithen ' transformed version is not in the language turing machines are simple model of computation for writing programs that are language acceptors there is "universalturing machine that can take as input description for turing machineand an input stringand return the execution of that machine on that string this turing machine in turn can be cast as boolean expression such that the expression is satisfiable if and only if the turing machine yields accept for that string cook used turing machines in his proof because they are simple enough that he could develop this transformation of turing machines to boolean expressionsbut rich enough to be able to compute any function that regular computer can compute the significance of this transformation is that any decision problem that is performable by the turing machine is transformable to sat thussat is -hard as explained aboveto show that decision problem is -completewe prove that is in (normally easyand normally done by giving suitable polynomial-timenondeterministic algorithmand then prove that is -hard to prove that is -hardwe choose known -complete problemsay we describe polynomial-time transformation that takes an arbitrary instance of to an instance of we then describe polynomial-time transformation from to such that is the solution for the following example provides model for how an -completeness proof is done