# P vs. NP Problem

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

`P`

Problem$P$ = the set of problems that are solvable in polynomial time. If the problem has size $n$, the problem should be solved in $n_{O(1)}$.

$NP$ = the set of decision problems solvable in nondeterministic polynomial time. The output of these problems is a YES or NO answer.

Nondeterministic refers to the fact that a solution can be guessed out of polynomially many options in $O(1)$ time. If any guess is a YES instance, then the nondeterministic algorithm will make that guess.

In this model of nondeterminism, we can assume that all guessing is done first. This is equivalent to finding a polynomial-time verifier of polynomial-size certificates for YES answers.

Note that there is an asymmetry between YES and NO inputs

A problem $X$ is **NP-complete** if $X∈NP$ and $X$ is NP-hard. See NP-Complete

A problem $X$ is **NP-hard** if every problem $Y∈NP$ reduces to $X$. See NP-Hard

- If $P=NP$, then $X∈/P$.

Remember the diagram that Erik Demaine drew. You have P, and then NP encapsultes P, and then on the other side you have NP-Hard. The vertical line at the intersection of NP and NP-Hard is NP-complete.

A **reduction** from problem $A$ to problem $B$ is a polynomial-time algorithm that converts inputs to problem $A$ into equivalent inputs to problem $B$. Equivalent means that both problem $A$ and problem $B$ must output the same YES or NO answer for the input and converted input.

- If $B∈P$, then $A∈NP$
- If $B∈NP$, then $A∈NP$
- If $A$ is NP-hard, then $B$ is NP-hard.

We can show that problems are NP-complete via the following steps:

- Show $X∈NP$. Show that $X∈NP$ by finding a nondeterministic algorithm, or giving a valid verifier for a certificate.
- Show $X$ is NP-hard. Reduce from a known NP-complete problem $Y$ to $X$. This is sufficient because all problems $Z∈NP$ can be reduced to $Y$, and the reduction demonstrates inputs to $Y$ can be modified to become inputs to $X$, which implies $X$ is NP-hard. We must demonstrate the following properties for a complete reduction. (a). Give an polynomial-time conversion from $Y$ inputs to $X$ inputs. (b) If $Y$’s answer is YES, then $X$’s answer is YES. (c) If $X$’s answer is YES, then $Y$ ’s answer is YES.

Finally, a gadget transforms features in an input problem to a feature in an output problem.

### Related

- 3SAT