Date: March 27, 2026

Topic: 3-$SAT$

<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>

Recall

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:

Notes

3-$SAT$

Input

Boolean formula $f$ in $CNF$ with $n$ variables & $m$ clauses, each clause has $\leq 3$ literals

Output

Satisfying assignment for the $CNF$ if one exists, otherwise output NO

Proving $NP$-completeness

To show that 3-$SAT$ is $NP$-complete:

  1. Show that 3-$SAT$ $\in NP$
  2. Show that we can reduce $SAT$ β†’ 3-$SAT$ and thus for all problems $A \in NP$, $A β†’$ 3-$SAT$

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.

Proving 3-$SAT$ $\in NP$

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$

Proving $SAT$ β†’ 3-$SAT$

We use the 3-$SAT$ algorithm as a sub-routine to $SAT$ (reduce $SAT$ to 3-$SAT$)

image.png


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.

Example Reduction

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)$

Input $f'$ for 3-$SAT$

Equivalent Clauses

Forward Proof Claim β€” ****$C_2$ is satisfiable $\rightarrow$ $C_2’$ is satisfiable

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

Reverse Proof Claim β€” $C_2$ is satisfiable $\leftarrow$ $C_2’$ is satisfiable

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.

General 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$ is satisfiable $\leftrightarrow$ $C'$ is satisfiable

$$ 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)} $$

Forward Claim ($C$ is satisfiable $\rightarrow$ $C'$ is satisfiable)

For an assignment to $a_1, …, a_k$ satisfying $C$, let $a_i$ be the minimum $i$ where $a_i$ is satisfied

Example

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

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

Reverse Claim ($C$ is satisfiable $\leftarrow$ $C'$ is satisfiable)

If all non-aux vars ($a$) were set to $F$, then we can never satisfy $C’$

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$



Date: March 28, 2026

Topic: Graphs β€” Independent Set

<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>