Understanding NPComplete
Definitions
We define the symbols in this section to prepare for explaining NPcomplete.

f(x):
f
is the problem. E.g. in the given graph G, list the SHORTESTPATH 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. 
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 transformf(x)
into a decision problem. For example, the SHORTESTPATH problem can be transform into: “Does there exists a path in graph G connecting V1 and V2, which is shorter than length k?” Oncef(x)
is solved,C(f(x))
is solved; sof(x)
is harder thanC(f(x))
(problem reduction).C(f(x))
is the NP problem we gonna discuss here. Note that by definition, an NP problemC
doesn’t necessarily need anf(x)
. 
A(x, y):
f(x)
says “find something”.C(f(x))
says “does the something exist?”. We name the “something” here asy
.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 asA(x, y)
here.A(x, y)
says: given the “something”y
, does it really satisfy whatC(f(x))
wants?A(x, y)
has polynomial time complexity. Finally the NP problemC(f(x))
can be seen as “does ay
that satisfiesA(x, y)
exist?”
What is NPcomplete
A decision problem C
is NPcomplete if

C
is a NP problem, and 
C
is equal or harder than any other NP problems (“hardness” is defined by problem reduction)
The first NPcomplete problem is the circuit satisfiability problem. To prove rule 2 for it

Every NP problem
C
has itsA(x, y)

Since
A(x, y)
is an algorithm of polynomial time complexity, we can construct its equivalent combinational logic circuit 
If there exists an
y
satisfyingA(x, y)
, the equivalenty
must satisfy our circuit, vice versa. The later one is the circuit satisfiability problem. 
So, if circuit satisfiability problem is solved, we know whether
y
exists, thus solvingC
. This means circuit satisfiability problem is equal or harder than any other NP problem.
An NPcomplete 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 NPcomplete set is that

NPcomplete problems are the hardest in the NP set

There are many NPcomplete problems, and they are of the same hardness.
To prove a NPcomplete problem
The NP problem to prove is C1
, which has verification algorithm A1(x, y)
. The general approach is to

Find an existing NPcomplete problem
C2
and itsA2(x, y)
. 
Given the
A2(x, y)
, construct its equivalentA1(x, y)
. So that if anyy
satisfiesA1(x, y)
, it satisfiesA2(x, y)
, and vice versa. This is the reduction. 
So that if we could solve
C1
, i.e. to know whether ay
satisfyingA1(x, y)
exists, we solveC2
. It meansC1
is no less harder thanC2
, thusC1
is NPcomplete.
For more about NPcomplete, refer to wiki or “Introduction of Algorithms”.
Create an Issue or comment below