P vs. NP

NP Class

A problem is in , if there is a polynomial time verification algorithm such that the input is a yes-instance iff there is a proof (certificate) which is a binary string of length so that returns yes.


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

Example 1: Vertex Cover

  • here is an input graph and an integer
  • here is a subset of with

: go through all and check if covers the edges and .

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 and a cycle, verify if the cycle is Hamiltonian (visits every vertex exactly once and returns to the start) in polynomial time.