np complete problem

NP-COMPLETE PROBLEM

NP-complete problem, are computational problems for which no efficient solution algorithm has been found. 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.

             There is a set of problems in NP for which if there’s a polynomial solution to one there will be a polynomial solution to all. The set is called NP-Complete

         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.

WHY NP-COMPLETE PROBLEM..?

A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (i.e. in polynomial time) transformed into x. In other words:

1. x is in NP, and
2. Every problem in NP is reducible to x

So what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly then all NP problems can be solved quickly.

EXAMPLE OF NP-COMPLETE PROBLEM

Some examples of NP-Complete problems are listed here;

•  Hamilton cycle
• The subset sum problem
• Traveling salesman problem
• Graph coloring problem
• Bin packing problem
• 0/1 knapsack problem

Here I choose the Graph coloring of NP-Complete problem;

 GRAPH COLORING

                   Clearly a graph can be constructed from any map, the regions being represented by the vertices of the graph and two vertices being joined by an edge if the regions corresponding to the vertices are adjacent. The resulting graph is planar, that is, it can be drawn in the plane without any edges crossing.

           Ex: A k-coloring of a graph G is an assignment of one color to each vertex of G such that no more than k colors are used and no two adjacent vertices receive the same color. A graph is called k-colorable iff it has a k-coloring.

Application of Graph Coloring Problem

1) Register allocation:

• want local variables in registers

• Each local variable represented as a node

• If the lifetime/scope of 2 variables overlaps, draw an edge between the two nodes

• can the variables be stored in the k available registers?

Example: for a 4-register CPU, can we store all local

Variables inside the for loop in the registers?

f (int n)

{

int i, j;

for (i = 0; i < n; i++) {

int u, v;

// . . . statements involving i, u, v

j = u + v;

}

}

Fig:3-colouring

Lines/Edges;

Two points (x1, y1), (x2, y2) form a line:
y − y1
x − x1
=
y2 − y1
x2 − x1
y =
y2 − y1
x2 − x1
(x − x1)+y1
y = mx+b
where m = y2−y1
x2−x1, and b = y1 −mx1
Careful that we are usually only dealing with a line segment
y3 = mx3 +b is on the above line segment iff:
MIN(x1, x2)  x3  MAX(x1, x2) and
MIN(y1, y2)  y3  MAX(y1, y2)

This proves that 3-colorability is a NP complete Problem