<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>
$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.
To verify instance $I$ with a given solution $S$, we use an algorithm that can do so in polynomial time for search problems.
Given an instance $I$:
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.
Boolean formula $f$ in CNF (conjunctive normal form) with $n$ variables & $m$ clauses
Satisfying assignment if one exists
$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$
Given $f$ and assignments of $T/F$ for $x_1, …, x_n$, what is the runtime to verify the solution as $T$?
Given $f$ and assignment to $x_1, …, x_n$:
<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>
$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.
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
Assign each vertex a color in $\{1, 2, …, k\}$ such that adjacent vertices get different colors
Given $G$ and a solution coloring: