Our next reduction is from satisfiability problem to 3-satisfiability problem. That is, from a general version of a problem to its special case. To construct such a reduction, we need to design a polynomial time algorithm that takes as input a formula in conjunctive normal form, that is, a collection of clauses, and produces an equisatisfiable formula in 3-CNF, that is, a formula in which each clause has at most three literals. By saying equisatisfiable, we mean that the resulting formula is satisfiable if and only if the initial formula is satisfiable. Once again, if the initial formula is F and the resulting formula is F prime, then by saying equisatisfiable, we mean that F is satisfiable if and only if F prime is satisfiable. To construct such a reduction, we need to somehow get rid of all long clauses in our formula. By saying long, we mean clauses that contain more that three literals. Right. To do this, consider such a long clause and denote by l1 and l2 some two literals of this clause and denote by A the rest of this clause. So once again, l1 and l2 are two literal of the clause C, which we consider at the moment. And A is the set of all other literals. Now we are going to do the following, introduce a new, fresh variable y and replace the current clause C with the following two clauses. So the first clause contains literals l1, l2, and y, so it is a disjunction of l1, l2, and y. The second clause contains a negation of y and all the other literals which we denote by a set A, okay? Then we first of all note an important property. The clause, the first of the two new clauses has length 3. So we are okay with it. We are happy with it. We do not need to get rid of it. At the same time, this clause is shorter than the following one. Exactly by one literal. Right? So we are going to repeat this procedure while there is at least one long clause. And for sure, we will stop at some point, because at each step, we reduce some long clause with a shorter one. We now need to prove that the constructed transformation is correct, that the constructed reduction is correct, and that it takes polynomial time. Concerning time, consider the running time, it is clear because at each iteration we'll replace a clause with a shorter one. This means that the total number of iterations is bounded from above by the total number of literals in all the clauses. This is clearly polynomial in the length of an input formula. To prove that the constructed reduction is correct, we're going to show that the initial formula F with a long clause is satisfiable if and only if the resulting formula where we replaced a long clause with a 3-clause and a shorter clause is also satisfiable. To do this, consider these two formulas. So this is F. It contains a long clause. And this is F prime that results from F by replacing this long clause with the following two clauses, l1, l2 and y, where y Is a fresh variable and a clause not y or A. I assume now that the formula F is satisfiable and take a satisfying assignment. We are now going to extend it so that it also satisfies the formula F prime. Recall that the only difference between the sets of variables of formulas F and F prime is the variable y. So our goal is to set y so that the resulting assignment satisfies all the clauses of the formula F prime. First of all, all the remaining clauses of F prime are satisfied by exactly the same assignment that satisfies the formula F, so our goal is to set y so that both the first two clauses are satisfied. I mean, both the first two clauses of the formula F prime. Okay, so to set the variable y, we just check whether the current satisfying assignment of the formula F satisfies one of the literals l1 or l2 or not. So if it satisfies these two literals, we set y to 0. In this case, the first clause of the formula F prime is satisfied by one of l1 or l2. The second clause, on the other hand, is satisfied by the variable y, right, because we've just assigned the value 0 to y. On the other hand, if l1 and l2 are falsified by the current satisfying assignment, then at least one of the literals from the set I should be satisfied. In this case, we just set the value of y to 1, right. In this case, the first clause is satisfied by the value of y while the second clause is satisfied by one of the literals from the set A. Okay, for the reverse direction, note that if we have a satisfying assignment that satisfies the formula F prime, then we can just discard the value of the variable y from this assignment, and then what we get is a satisfying assignment for the formula F. Why is that? Well, for a simple reason. What we need to show is that this clause is satisfied in a formula F, but it must be satisfied, because at least one of l1, l2, and all the literals of A should be satisfied. Assume for the sake of contradiction that in the current satisfying assignment for F prime, l1 is set to 0, l2 is set to 0, and all the literals from the set A are also set to 0. Then there is just no possibility to satisfy these two clauses because no matter how we assign the value to y either the first clause or the second clause is going to be unsatisfied.