# NP Class

A problem $X$ is in $NP$, if there is a **polynomial time verification algorithm** $ALG_{X}$ such that the input $S$ is a yes-instance iff there is a proof (certificate) $t$ which is a binary string of length $poly(∣S∣)$ so that $ALG_{X}(S,t)$ returns yes.

Warning

This doesn’t mean that this proof $t$ can be found in polynomial time (that’s P-class problem).

Example 1: Vertex Cover

- $S$ here is an input graph $G=(V,E)$ and an integer $k$
- $t$ here is a subset $U$ of $V$ with $∣U∣≤k$
$Algv(S,t)$: go through all $E$ and check if $t$ covers the edges and $t≤k$.

At the core of it....

NP problem: “If you give me a solution, I can verify it in polynomial time.”

Isn't every problem NP?

No, some problems aren’t NP, because the certificate can’t be generated in polynomial time. For example, showing that a graph is non-hamiltonian (source).

**Hamiltonian Cycle:** Given a graph $G$ and a cycle, verify if the cycle is Hamiltonian (visits every vertex exactly once and returns to the start) in polynomial time.