Date: March 24, 2026

Topic: Introduction to NP and 2-$SAT$

<aside> 📌 SUMMARY:

$P$: Problems that are solvable in polynomial time $NP$: Solution to the problems are verified in polynomial time If $P=NP$, then every problem whose solution can be verified in polynomial time can also be solved in polynomial time.

$SAT$ problems are considered $NP$, since we can verify their solutions in polynomial time when the solution is given.

</aside>

Recall

$P$: Problems that are solvable in polynomial time

$NP$: Problem whose proposed solutions can be verified in polynomial time

If $P=NP$, then every problem whose solution can be verified in polynomial time can also be solved in polynomial time.

Notes

Complexity Classes

$P$ vs. $NP$


To verify instance $I$ with a given solution $S$, we use an algorithm that can do so in polynomial time for search problems.

Search Problems

Form

Given an instance $I$:

Requirement for a Search Problem

If given an instance $I$ and a solution $S$:


For the $SAT$ problem, we need to find a value for each variable such that each clause and thus the whole CNF outputs $T$.

Verifying the solution of the $SAT$ problem takes $O(nm)$, where $n$ is the number of variables and $m$ is the number of clauses.

Satisfiability Problem

Input

Boolean formula $f$ in CNF (conjunctive normal form) with $n$ variables & $m$ clauses

Output

Satisfying assignment if one exists

Example

$f = (x_3 \vee \overline{x_2} \vee \overline{x_1}) \wedge (x_1) \wedge (x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_3})$

To satisfy this (every clause needs to be satisfied), we need $x_1 = T$, $x_2 = F$, $x_3 = F$

Evaluation ($SAT$ $\in NP$)

Given $f$ and assignments of $T/F$ for $x_1, …, x_n$, what is the runtime to verify the solution as $T$?

Proving that $SAT$ $\in NP$

Given $f$ and assignment to $x_1, …, x_n$:


Date: March 26, 2026

Topic: $k$-Colorings, $MST$ and Knapsack Problems

<aside> 📌 SUMMARY: For the $k$-colorings and $MST$ problem, they are considered to be $\in NP$ as their solutions can be verified in polynomial time. While Knapsack itself is not considered to be in $NP$, Knapsack-search, which has an additional goal $g$ where the sum of values has to be at least greater, is considered to be $\in NP$.

</aside>

Recall

$k$-colorings is considered to be in $NP$ since we can verify a solution by checking that for all edges, the color of the 2 endpoints (nodes) are not the same. This can be done in $O(m)$ time.

Notes

$k$-Colorings Problem

Input

For an undirected graph $G=(V,E)$ and integer $k > 0$, we want to assign colors to vertices such that their neighbors have different colors

Output

Assign each vertex a color in $\{1, 2, …, k\}$ such that adjacent vertices get different colors

Evaluation ($k$-Colorings $\in NP$)

Given $G$ and a solution coloring: