Why NP is nice [cpsc/why-np]

We’ll spend the next couple of lectures talking about Np (complexity class). Why? Nondeterministic Turing machines are ridiculously impractical!

Many problems that we’re interested in have the form $L = \left\{ {x:\exists y,|y| \leq |x|^{c},V\ \text{accepts}\ \left( {x,y} \right)} \right\}$ (where $x$ is the problem input and $y$ is the object we are seeking).

Efficient test: is $y$ a valid solution?

We showed 3COLOR $\in$ Np (complexity class).

• Claim: Clique $\in$ Np (complexity class) (Clique={⟨𝐺,𝐾⟩:𝐺contains acliqueof size𝑘})
• Claim: Hampath $\in$ Np (complexity class) (Hamiltonian path problem)

Np (complexity class) has lots of problems that are interesting and nice to solve, but that we don’t know of any polynomial time solution. But: if any of these problems are in P (complexity class), then all of them are in P (complexity class). NP-completeness!