P vs. NP

NP Class

A problem $X$ is in $NP$, if there is a polynomial time verification algorithm $AL{G}_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 $AL{G}_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|\le k$

$Algv(S,t)$: go through all $E$ and check if $t$ covers the edges and $t\le 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.

Next

• NP-Complete