Why NP is nice [cpsc/why-NP]

We’ll spend the next couple of lectures talking about NP. Why?

Because 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

• Claim: Clique $\in$ Np (complexity class) ($\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{contains a clique of size}\ k} \right\}$)
• 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, then all of them are in P. NP-completeness!