<aside> π SUMMARY: To show that 3-$SAT$ is $NP$-complete, we show that 3-$SAT \in NP$ reduce a known $NP$-complete problem to it, such as $SAT$. This allows us to then treat the 3-$SAT$ algorithm as a black-box which takes in a converted input and produces an output that needs to be converted back for the original input.
For each clause in $SAT$ that has $> 3$ literals, we apply a conversion by creating $k-3$ ****new variables $y_1, y_2, β¦, y_{k-3}$ and replace $C$ by $k-2$ clauses. Satisfiability can be shown either way, where $C$ is satisfiable $\leftrightarrow$ $Cβ$ is satisfiable.
To obtain the correct output for the original problem, we just discard the additional literals (and their values) added.
</aside>
In 3-$SAT$, we have to show that there is a satisfying assignment for the CNF using 3 literals.
To prove it is $NP$-complete, we need to:
Boolean formula $f$ in $CNF$ with $n$ variables & $m$ clauses, each clause has $\leq 3$ literals
Satisfying assignment for the $CNF$ if one exists, otherwise output NO
To show that 3-$SAT$ is $NP$-complete:
For each clause, we only check 3 literals, so it takes $O(1)$ time per clause. To verify $m$ clauses, we thus take $O(m)$ time to verify the solution.
We can show that the solution to 3-$SAT$ can be verified in polynomial time.
Given a 3-$SAT$ input and a $T / F$ assignment for $x_1, β¦, x_n$:
We have a satisfying assignment for 3-$SAT$ iff we have a satisfying input for $SAT$ formula. $\sigma' \space \text{satisfies} \space f' \leftrightarrow \sigma \space \text{satisfies} \space f$
We use the 3-$SAT$ algorithm as a sub-routine to $SAT$ (reduce $SAT$ to 3-$SAT$)

To reduce $SAT$ to 3-$SAT$, we need to convert all clauses with more than 3 literals to clauses with at most 3 literals.
For example, we can do the following conversion: $C_2 =(\overline{x_2}\vee x_3 \vee \overline{x_1}\vee \overline{x_4})$ β $C_2' = (\overline{x_2}\vee x_3 \vee y)\land(\overline{y}\vee \overline{x_1}\vee \overline{x_4})$
In the forward proof claim, show if $C_2$ is satisfied, then $C_2β$ can be satisfied. In the reverse proof claim, show if $C_2β$ is satisfied, then $C_2$ is satisfied.
If we have a SAT problem with 3 clauses: $f = (x_3)\land(\overline{x_2}\vee x_3 \vee \overline{x_1}\vee \overline{x_4})\land(x_2\vee x_1)$
Given a satisfying assignment for $C_2$, can we get a satisfying assignment for $C_2'$? We satisfy $C_2$ and check if the equivalent for $C_2'$ can be satisfied
Now the other way; given a satisfying assignment for $C_2'$, can we get a satisfying assignment for $C_2$? We satisfy $C_2'$ and check if the equivalent for $C_2$ can be satisfied
For converting $SAT$ to 3-$SAT$, if we have any clause that has more than 3 literals, we use the form:
If there are only 4 literals, then we just use the first and last clause form.
For a SAT clause with many literals; $C = (a_1 \vee a_2 \vee β¦ \vee a_k)$ where $a_1, a_2,β¦,a_k$ are literals
Thus we get a general pattern as follows:
$$ C' = \blue{(a_1 \vee a_2 \vee y_1)}\;\wedge\;(\overline{y_1} \vee a_3 \vee y_2)\;\wedge\;(\overline{y_2} \vee a_4 \vee y_3)\;\wedge\;\cdots\;\wedge\;(\overline{y_{k-4}} \vee a_{k-2} \vee y_{k-3})\;\wedge\;\orange{(\overline{y_{k-3}} \vee a_{k-1} \vee a_k)} $$
$$ C = (a_1 \vee a_2 \vee β¦ \vee a_k) \leftrightarrow C' = \blue{(a_1 \vee a_2 \vee y_1)}\;\wedge\;(\overline{y_1} \vee a_3 \vee y_2)\;\wedge\;(\overline{y_2} \vee a_4 \vee y_3)\;\wedge\;\cdots\;\wedge\;(\overline{y_{k-4}} \vee a_{k-2} \vee y_{k-3})\;\wedge\;\orange{(\overline{y_{k-3}} \vee a_{k-1} \vee a_k)} $$
For an assignment to $a_1, β¦, a_k$ satisfying $C$, let $a_i$ be the minimum $i$ where $a_i$ is satisfied

If minimum $i = 4$, $a_4$ is $T$, and thus we can set all aux. vars. accordingly

If all non-aux vars ($a$) were set to $F$, then we can never satisfy $Cβ$
Take an assignment to $a_1,β¦,a_k$, $y_1,β¦,y_{k-3}$ that satisfies $Cβ$ β we need at least 1 literal from $a_1,β¦,a_k$ to be $T$
<aside> π SUMMARY: For a set of nodes to be independent, they must not be connected by any edge. We are interested in finding such a set that is maximized. However, since this problem is not known to be $NP$-complete, we introduce an additional goal $g$ instead, where the solution $|S| \geq g$.
</aside>