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 Problem

$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\in NP$ and $X$ is NP-hard. See NP-Complete

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

• If $P\ne NP$, then $X\notin 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\in P$, then $A\in NP$
• If $B\in NP$, then $A\in NP$
• If $A$ is NP-hard, then $B$ is NP-hard.

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

1. Show $X\in NP$. Show that $X\in NP$ by finding a nondeterministic algorithm, or giving a valid verifier for a certificate.
2. Show $X$ is NP-hard. Reduce from a known NP-complete problem $Y$ to $X$. This is sufficient because all problems $Z\in 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