NP-Complete

Informally we say a problem is NP-complete if it is the hardest problem in NP.

A problem $X$ is NP-complete if $X\in NP$ and $X$ is NP-Hard.

From CS341

A problem $X\in NP$ is $NP$-complete if $Y{\le }_{P}X$ for all $Y\in NP$.

A problem is NP-complete when: it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

NP-Complete Problems proven and shown that we can use during exam:

• 3SAT, SAT
• Independent set, vertex cover, clique
• (directed) Hamiltonian cycle, Hamiltonian path
• traveling salesman
• Subset Sum
• 0/1 Knapsack
• 3-CNF

A Hamiltonian cycle of a directed graph $G=(V,E)$ is a simple cycle that contains each vertex in $V$. Determining whether a directed graph has a hamiltonian cycle is NP-complete.

NP-completeness and the classes P and NP

P class consists of those problems that are solvable in polynomial time. Any problem in P is also in NP, since if a problem is in P, then we can solve it in polynomial time without even being supplied a certificate.

We define the complexity class P as the set of concrete decision problems that are polynomial-time solvable.

The class NP consists of those problems that are “verifiable” in polynomial time.

A problem is in NPC, if it is in NP and is as “hard” as any problem in NP.

What does it mean to be as hard as any problem in NP?

Overview of showing problems to be NP-complete

If you can demonstrate that a problem is NP-complete, you are making a statement about how hard it is. We are not trying to prove the existence of an efficient algorithm, but instead that no efficient algorithm is likely to exist.

NP- completeness applies directly not to optimization problems, but decisions problems, in which the answer is simply “yes” or “no”.

If an optimization problem is easy, its related decision problem is easy as well. So in regard to NP-completeness, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard.

Reductions

The above notion of showing that one problem is no harder or no easier than an- other applies even when both problems are decision problems.

Proof for NP-completeness takes advantages of this idea:

Consider a decision problem $A$, which you would like to solve in polynomial time. We call the input to a particular problem an instance of that problem. Now suppose that you already know how to solve a different decision problem in polynomial time. Finally, suppose that you have a procedure that transforms any instance $\alpha$ of $A$ into some instance $\beta$ of $B$ with the following characteristics:

• The transformation takes polynomial time.
• The answers are the same. That is, the answer for $\alpha$ is “yes” if and only if the answer for $\beta$ is also “yes”.

We call such a procedure a polynomial-time reduction algorithm and, it provides us a way to solve problem $A$ in polynomial time:

1. Given an instance $\alpha$ of problem $A$, use a polynomial-time reduction algorithm to transform it to an instance $\beta$ of problem $B$.
2. Run the polynomial-time decision algorithm for $B$ on the instance $\beta$.
3. Use the answer for $\beta$ as the answer for $\alpha$.

As long as each of these steps takes polynomial time, all three together do also, and so you have a way to decide on in polynomial time. In other words, by “reducing” solving problem $A$ to solving problem $B$, you use the “easiness” of $B$ to prove the “easiness” of $A$.

Recalling that NP-completeness

Is about showing how hard a problem is rather than how easy it is, you use polynomial-time reductions in the opposite way to show that a problem is NP-complete.

Suppose that you have a decision problem $A$ for which you already know that no polynomial-time algorithm can exist. (Ignore for the moment how to find such a problem .) Suppose further that you have a polynomial-time reduction transforming instances of $A$ to instances of $B$. Now you can use a simple proof by contradiction to show that no polynomial-time algorithm can exist for $B$. Suppose otherwise, that is, suppose that $B$ has a polynomial-time algorithm. Then, using the method shown in Figure 34.1, you would have a way to solve problem in polynomial time, which contradicts the assumption that there is no polynomial-time algorithm for .

To prove that a problem $B$ is NP-complete, you cannot assume that there is absolutely no polynomial-time algorithm for problem $A$, you prove that problem $B$ is NP-complete on the assumption that problem $A$ is also NP-complete.