16 June 2015

### Definitions

We define the symbols in this section to prepare for explaining NP-complete.

1. f(x): `f` is the problem. E.g. in the given graph G, list the SHORTEST-PATH beween V1 and V2. `x` is the input for this problem. E.g. the graph G and V1, V2. Usually, `f(x)` can be an optimization problem.

2. C(f(x)) -> {0, 1}: NP theory discusses only decision problem, i.e. a problem which outputs only yes or no (1 or 0). So we need `C` to transform `f(x)` into a decision problem. For example, the SHORTEST-PATH problem can be transform into: “Does there exists a path in graph G connecting V1 and V2, which is shorter than length k?” Once `f(x)` is solved, `C(f(x))` is solved; so `f(x)` is harder than `C(f(x))` (problem reduction). `C(f(x))` is the NP problem we gonna discuss here. Note that by definition, an NP problem `C` doesn’t necessarily need an `f(x)`.

3. A(x, y): `f(x)` says “find something”. `C(f(x))` says “does the something exist?”. We name the “something” here as `y`. `y` is called certificate in NP theory. According to the denifition of NP, `C(f(x))` should be verifiable in polynomial time. We name its verification algorithm as `A(x, y)` here. `A(x, y)` says: given the “something” `y`, does it really satisfy what `C(f(x))` wants? `A(x, y)` has polynomial time complexity. Finally the NP problem `C(f(x))` can be seen as “does a `y` that satisfies `A(x, y)` exist?”

### What is NP-complete A decision problem `C` is NP-complete if

1. `C` is a NP problem, and

2. `C` is equal or harder than any other NP problems (“hardness” is defined by problem reduction)

The first NP-complete problem is the circuit satisfiability problem. To prove rule 2 for it

1. Every NP problem `C` has its `A(x, y)`

2. Since `A(x, y)` is an algorithm of polynomial time complexity, we can construct its equivalent combinational logic circuit

3. If there exists an `y` satisfying `A(x, y)`, the equivalent `y` must satisfy our circuit, vice versa. The later one is the circuit satisfiability problem.

4. So, if circuit satisfiability problem is solved, we know whether `y` exists, thus solving `C`. This means circuit satisfiability problem is equal or harder than any other NP problem.

An NP-complete problem is the hardest problem in NP set. The true magic is that, later people found many other problems are no less harder than the circuit satisfiability problem (proved by problem reduction, see below); i.e. they are off the same hardness. So the truth of NP-complete set is that

1. NP-complete problems are the hardest in the NP set

2. There are many NP-complete problems, and they are of the same hardness.

### To prove a NP-complete problem

The NP problem to prove is `C1`, which has verification algorithm `A1(x, y)`. The general approach is to

1. Find an existing NP-complete problem `C2` and its `A2(x, y)`.

2. Given the `A2(x, y)`, construct its equivalent `A1(x, y)`. So that if any `y` satisfies `A1(x, y)`, it satisfies `A2(x, y)`, and vice versa. This is the reduction.

3. So that if we could solve `C1`, i.e. to know whether a `y` satisfying `A1(x, y)` exists, we solve `C2`. It means `C1` is no less harder than `C2`, thus `C1` is NP-complete.

For more about NP-complete, refer to wiki or “Introduction of Algorithms”.

Create an Issue or comment below