NP-Completeness

It appears that although I know $P$ and I sort of know $NP$, I do not quite have a firm grasp of complexity theory as I would like. So this blog is an attempt to clarify (revisit) complexity. It is not by any means complete.

Proving NP-Completeness

Let us start backward with the idea of trying to prove that a problem is $NP$-Complete. So the statement goes as followed. To prove a problem $X$ is $NP$-complete: first, show that the problem is $NP$; second, show that it is at least as hard (if not harder) than any other $NP$ problem.

1. Problem $X$ is $NP$

To show that a problem is $NP$, we would need to show that we have a polynomial time algorithm that can verify whether or not a solution is correct. To formally define $NP$, we say that a problem is $NP$ if:

  • Its solution comes from a finite set of possibilities, and
  • It takes polynomial time to verify the correctness of a candidate solution

Intuitively, we are saying that if an answer magically shows up, we can in polynomial time respond: “yes, this answer is correct” or “no, this answer is not correct.”

There is yet another way to define $NP$: A problem is $NP$ if there is an $NP$ algorithm for it.

2. Problem $X$ is $NP$-hard

To show that a problem is $NP$ hard is slightly trickier. The argument goes as followed, if there is a known $NP$ hard problem that can be in polynomial time transformed into our problem then our problem must be $NP$ hard. Otherwise, there would be a polynomial time solution for that problem.

This involves identifying a problem $Y$ that has already been proven to be $NP$-complete and that there is a polynomial time algorithm that transforms $Y$ to $X$. Or as my friend Darren would say, is there a way to embed problem $Y$ in problem $X$?

Natually, one could make a case that if we can represent our problem as an $NP$ hard problem, is that necessary and sufficient, to say that our problem is $NP$-complete? Not likely.

Decision Problems

A decision problem is also known as a “Yes-No” problem. The nature of these problems dictates that given a problem, the only answer that is of interest is “yes” or “no”. One should note that all $NP$-complete problems can be restated as “Yes-No” problems.

Vertex Cover

Let us take for granted that the Vertex Cover problem is $NP$-complete as it has already been proven by Karp, and later on regurgitated by many others. Here, we are only trying to describe and understand what is a vertex cover problem.

A vertex cover of a graph is a set of vertices such that each each edge of the graph is incident (connected) to at least one vertex in the set.

To ask “Is there a vertex” cover for the graph is a “Yes-No” decision problem. Alternatively, to ask “Find the minimum vertex-cover” is an optimization problem.

Subset Sum

Let us prove that the subset sum problem is $NP$-complete. First, define the subset sum problem:

  • Given a sequence of integers $a_1,\ldots,a_n$ and a parameter $k$
  • Determine whether there is a subset of integers whose sum is exactly $k$.

Formally: Is there a subset $I \subseteq 1,\ldots,n$ such that $\sum_{i\in I} a_i = k$.

This is a “Yes-No” problem given that the question asked “Is there…”. To prove that Subset sum is $NP$-complete we would need to map the vertex cover to the subset problem in polynomial time.

(more to come…)

References