NP-complete problem, are computational problems for which no efficient solution
algorithm has been found. Many
significant computer-science problems belong to this class—e.g., the traveling salesman
problem, satisfiability problems, and graph-covering problems.
So-called easy, or tractable,
problems can be solved by computer algorithms that run in polynomial time; i.e.,
for a problem of size n, the time or number of steps
needed to find the solution is a polynomial function of n. Algorithms for solving hard,
or intractable, problems,
on the other hand, require times that are exponential
functions of the problem size n.
A problem is called NP (non-deterministic polynomial) if its solution can be guessed and verified in
polynomial time; non-deterministic means that no particular rule is followed to
make the guess. If a problem is NP and all other NP problems are polynomial-time
reducible to it, the problem is NP-complete.
NP-complete
In complexity theory, the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most
likely not to be in P. The reason is that if you could find a
way to solve an NP-complete problem quickly, then you could use that algorithm
to solve all NP problems quickly.
One example of an NP-complete problem is the subset sum problem which
is: given a finite set of integers, determine whether any non-empty subset of
them adds up to zero. A supposed answer is very easy to verify for correctness,
but no-one knows a faster way to solve the problem than to try every single
possible subset, which is very slow.
At present, all known algorithms for NP-complete
problems require time which is exponential in the problem size. It is unknown
whether there are any faster algorithms. Therefore, in order to solve an
NP-complete problem for any non-trivial problem size, one of the following
approaches is used:
- Approximation: An algorithm which quickly finds a sub-optimal solution
which is within a certain (known) range of the optimal one. Not all
NP-complete problems have good approximation algorithms, and for some
problems finding a good approximation algorithm is enough to solve the
problem itself.
- Probabilistic: An algorithm which provably yields good average
runtime behavior for a given distribution of the problem
instances—ideally, one that assigns low probability to "hard"
inputs.
- Special
cases: An algorithm which is
provably fast if the problem instances belong to a certain special case
- Heuristic: An algorithm which works "reasonably well"
on many cases, but for which there is no proof that it is always fast.
Formal
definition of NP-completeness
A decision problem C is NP-complete if it is in NP and if
every other problem in NP is reducible to it. "Reducible" here means
that for every NP problem L,
there is a polynomial-time algorithm which transforms instances of L into instances of C, such that the two
instances have the same truth values. As a consequence, if we had a polynomial
time algorithm for C, we
could solve all NP problems in polynomial time.
In mathematical terms,
- L in NP
- L' ≤ L for every L' in NP
This definition was
given by Stephen Cook.
It isn't really correct to say that NP-complete problems are
the hardest problems in NP. Assuming that P and NP are not equal, there are
guaranteed to be an infinite number of problems that are in NP, but are neither
NP-complete nor in P. Some of these problems may actually have higher
complexity than some of the NP-complete problems.
Example : Hamilton Cycle
A Hamilton cycle is a cycle in the graph that visits every
vertex exactly once.
There are two versions of the Directed Hamilton
Cycle Problem.
The function version:
Given a directed graph G with n vertices
find a Hamilton Cycle in G.
The decision version:
Given a directed graph G with n vertices
determine if G has a Hamilton Cycle.
Theorem : Both versions of the Directed Hamilton Cycle problem are
NP-complete.
Proof : The Function Version
of the Problem is Reducible to the Decision Version of the Problem. The algorithm described below
solves the function version of the problem with O(n2) calls
of the decision version of the problem.
Input: The directed graph G
Output: A Hamilton Cycle in G if
one exists or "no solution" if it doesn't.
Auxiliary Function: f( G)→{0,1} f( G)=1 iff G has
a Hamilton Cycle.
If f( G)=0 v0 .
The solution path starts at v0 .
While G has
more then one vertex:
Pick one of the edges going out of v0 .
Call that edge (v0,u) .
If f( G−(v0,u ))=1 remove (v0,u) from G
Otherwise add u to
the end of the solution set and remove the vertices v0 and u from G and
replace them with a new v0 where (v0,w) is
in the new graph if (u,w) is
in the old graph, and (w,v0) is
in the new graph if (w,v0) is
in the old graph. Finally add v0 to
the end of the solution path and we have our solution. Because every time f( G) is
calculated at least one edge is removed f( G) is
called O(n2) times.
This algorithm shows the functional problem polynomially reduces to the
decision problem. The functional problem also reduces to the the decision
problem because if the output of the functional problem is anything other then
"no solution" then G has
a Hamilton Cycle. Because they are mutually polynomially reducible we can show
that both are NP or NP-hard by showing that either of them are NP or NP-hard.
The Directed Hamilton Cycle Problem is NP
Given a potential
solution to the decision problem in the form of a sequence of vertices it is
possible to determine if that sequence is a Hamilton Cycle by making sure every
vertex appears exactly once and verifying that each vertex in the sequence follows
is adjacent to the previous vertex.Because a potential solution can be verified
or rejected in polynomial time the
Hamilton Cycle Problem is NP.
The Directed Hamilton Cycle Problem is NP-hard
Consider the following diagram of a part
of a graph:
It is clear that either (A,B) or (B,A) must
be included in any Hamilton Cycle. Likewise either (C,D) or (D,C) must
be included. The three cases for these four vertices are:
(A,B,C,D)
(A,B,E,C,D)
(D,C,B,A)
In short, the four vertices A,B,C,D must
be visited in order or in reverse order. Also, they can only visit the E node
if they are in the right order. These pieces of the graph can be concatenated
by letting the D node of one piece be the same as the A node
of the next. The final graph to be constructed takes a form
similar to the following diagram
The boxes represent concatenations of the pieces we have
just studied. In the final graph there will be one of these rows for every
variable in the CNF SAT problem, each one linked to another row as shown here.
(This creates a circuit through the rows.) A left to right path corresponds to
the variable being true and a right to left path corresponds to the variable
being false.
In
addition to these vertices there will also be one vertex for every clause in
the original problem. These will take the E vertex position in
the first diagram. A vertex will have be attached to a pair of vertices in a
row if the variable the row corresponds to appears in the clause, going left to
right if the variable is not negated and right to left if it is negated. In the image the E type node would contain x1∨¬x2 if the first row corresponded to x1, and the second to x2.
Clearly
all the vertices could only be visited in a cycle if there was some choice of
direction for each of the rows that allowed all the E type
vertices to be visited. That would only happen if there was some way of
deciding values for the variables in the CNF SAT problem that gave each clause
at least one true variable in its conjunction. And so the graph has a Hamilton
Cycle iff the CNF SAT problem has a solution.
The
number of vertices in a given row is at most 3l+3 because each
variable can only appear in each clause once (Otherwise that clause is either
internally redundant or trivially satisfied), each additional instance of a
variable only requires three additional vertices, and there are only three
nodes of overhead. The number of E type vertices is l.
Therefore the total number of vertices in the constructed graph is at most 3lm+3m+l vertices.
Because the size of the graph is bounded by a polynomial of the size of the CNF
SAT problem this scheme is a polynomial reduction from CNF SAT to the directed
Hamilton Cycle problem.
The Directed Hamilton Cycle problem is NP-hard. Because the Directed Hamilton Cycle
problem is NP and NP-hard it is NP-complete
No comments:
Post a Comment