How to prove that a problem is NP complete?

Question

To show a problem is NP complete, you need to:

Show it is in NP

In other words, given some information C, you can create a polynomial time algorithm V that will verify for every possible input X whether X is in your domain or not.

Example

Prove that the problem of vertex covers (that is, for some graph G, does it have a vertex cover set of size k such that every edge in G has at least one vertex in the cover set?) is in NP:

• our input X is some graph G and some number k (this is from the problem definition)

• Take our information C to be "any possible subset of vertices in graph G of size k"

• Then we can write an algorithm V that, given G, k and C, will return whether that set of vertices is a vertex cover for G or not, in polynomial time.

Then for every graph G, if there exists some "possible subset of vertices in G of size k" which is a vertex cover, then G is in NP.

Note that we do not need to find C in polynomial time. If we could, the problem would be in `P.

Note that algorithm V should work for every G, for some C. For every input there should exist information that could help us verify whether the input is in the problem domain or not. That is, there should not be an input where the information doesn't exist.

Prove it is NP Hard

This involves getting a known NP-complete problem like SAT, the set of boolean expressions in the form:

(A or B or C) and (D or E or F) and ...

where the expression is satisfiable, that is there exists some setting for these booleans, which makes the expression true.

Then reduce the NP-complete problem to your problem in polynomial time.

That is, given some input X for SAT (or whatever NP-complete problem you are using), create some input Y for your problem, such that X is in SAT if and only if Y is in your problem. The function f : X -> Y must run in polynomial time.

In the example above, the input Y would be the graph G and the size of the vertex cover k.

For a full proof, you'd have to prove both:

• that X is in SAT => Y in your problem

• and Y in your problem => X in SAT.

marcog's answer has a link with several other NP-complete problems you could reduce to your problem.

Footnote: In step 2 (Prove it is NP-hard), reducing another NP-hard (not necessarily NP-complete) problem to the current problem will do, since NP-complete problems are a subset of NP-hard problems (that are also in NP).

You need to reduce an NP-Complete problem to the problem you have. If the reduction can be done in polynomial time then you have proven that your problem is NP-complete, if the problem is already in NP, because:

It is not easier than the NP-complete problem, since it can be reduced to it in polynomial time which makes the problem NP-Hard.

See the end of http://www.ics.uci.edu/~eppstein/161/960312.html for more.

In order to prove that a problem L is NP-complete, we need to do the following steps:

1. Prove your problem L belongs to NP (that is that given a solution you can verify it in polynomial time)
2. Select a known NP-complete problem L'
3. Describe an algorithm f that transforms L' into L
4. Prove that your algorithm is correct (formally: x ∈ L' if and only if f(x) ∈ L )
5. Prove that algo f runs in polynomial time

First, you show that it lies in NP at all.

Then you find another problem that you already know is NP complete and show how you polynomially reduce NP Hard problem to your problem.

1. Get familiar to a subset of NP Complete problems
2. Prove NP Hardness : Reduce an arbitrary instance of an NP complete problem to an instance of your problem. This is the biggest piece of a pie and where the familiarity with NP Complete problems pays. The reduction will be more or less difficult depending on the NP Complete problem you choose.
3. Prove that your problem is in NP : design an algorithm which can verify in polynomial time whether an instance is a solution.