chap limits to computation -satisfiability ( satinputa boolean expression in cnf such that each clause contains exactly literals outputyes if the expression can be satisfiedno otherwise example sat is special case of sat is sat easier than satnot if we can prove it to be -complete theorem sat is -complete proofprove that sat is in pguess (nondeterministicallytruth values for the variables the correctness of the guess can be verified in polynomial time prove that sat is -hardwe need polynomial-time reduction from sat to sat let ck be any instance of sat our strategy is to replace any clause ci that does not have exactly three literals with set of clauses each having exactly three literals (recall that literal can be variable such as xor the negation of variable such as let ci xj where xj are literals so ci replace ci with ci ( ( ( ( zwhere and are variables not appearing in clearlyci is satisfiable if and only if ( is satisfiablemeaning that is true so ci ( replace ci with ( ( zwhere is new variable not appearing in this new pair of clauses is satisfiable if and only if ( is satisfiablethat iseither or must be true replace ci ( xj with ( ( ( *(xj- zj- zj- (xj- xj zj- where zj- are new variables after appropriate replacements have been made for each ci boolean expression results that is an instance of sat each replacement is satisfiable if and only if the original clause is satisfiable the reduction is clearly polynomial time