NP Complete problem with example

 The computational complexity theory deals with the resources such as time, space or memory required during computation to solve a given problem. The computational theory is classified into groups as shown below:

Polynomial  Problems(P): 
         This class of problems are Decision problems that can be solved in polynomial time by deterministic algorithms.

NP class: 
         This class contains problems that can be solved in polynomial time by non-deterministic algorithms. The NP-class problems are divided as NP Complete and NP Hard.

NP Complete problems: 
         The NP Problems(non deterministic polynomial time) are NP Complete if their solutions can be verified quickly for correctness and if the same solving algorithm used can solve all other NP problems.

NP hard problems: 
          Problems that are at least as hard as the hardest problem in NP. A problem H is said to be NP hard if there is an NP complete problem that can be solved in a polynomial time.

Example of NP Complete problem – 3 Colorability  

3-colorability:  
       Given an undirected graph G(V,E),where V represents nodes and E represents edges, the problem of 3-colorability consists in finding an assignment of one of 3 possible colors to each node(V) of G such that no two adjacent nodes(V) have the same color.

        To prove that the problem of determining whether or not a graph is 3-colorable is NP-Complete, we need to show that it belongs to NP. we  need to "guess" the color of each vertex. We can then verify that our guess was a 3-coloring of the graph by simply looking at each edge. Now we need to show how to reduce a problem that is already known to be NP-Complete to the graph 3-colorability problem. The problem we will use is called 3-Satisfiability. It is a version of the Satisfiability problem in which every clause contains exactly 3 variables.

We need to show that, given an instance of 3-satisfiability, we can construct an "equivalent" instance of the Graph 3-colorability problem i.e., We can assign true/false values to every variable in the instance of satisfiability, so that every clause evaluates to true if and only if the vertices of the graph are colored using 3 colors, such that no edge has both endpoints of the  same color.

        This allows us to solve the instance of Satisfiability by constructing the graph, and then checking whether or not we can color it. If so, the instance of Satisfiability was satisfiable; if not, it wasn't.

Construction of 3-satisfiability:.

First, we create a triangle, whose vertices we will call true, false and red. These names will also be the names we will give to the color that gets used for these vertices when the graph is 3-colored. Then for every variable xi that appears in the instance of Satisfiability, we connect a vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated in below figure.

Let us also create a little piece of the graph for each clause. This piece of the graph will look like the one in the figure below. Here, we have for the clause "x1 or x2 or x3".
The gadget:

• This is a classic reduction that uses a “gadget”.

• Assume the outer vertices are colored at most two colors.

The gadget is 3-colorable if and only if the

outer vertices are not all the same color.

This part of the graph has an interesting property: the only ways to color it with the colors true, false and red, without having an edge whose two endpoints have the same color, is to use the color true for at least one of the vertices at the top. Conversely, if you assign colors true and false to the three vertices at the top, then as long as at least one of them was colored true, then you will be able to color the rest of the graph.

        Let us now prove that we can color the graph using 3 colors if and only if the instance of Satisfiability is satisfiable.

• Suppose first that the instance of Satisfiability is satisfiable. That is, we can assign the values true andfalse to the variables, so that every clause evaluates to true. We can color the graph as follows:
• If variable xi was assigned the value true, then we color vertex xi true, and vertex xi false. And vice versa.
• Clearly the two endpoints of our edges are not colored with the same color yet, and the only vertices that still have to be colored are those inside the pieces of the graphs. Since every clause is satisfied by our choice of values for the variables, this means that at least one of the three vertices at the top is colored true. Hence we can color the rest of these using the three colors.
• Now suppose that the graph can be colored using 3 colors. We assign the value true to a variable xi if the vertex xi was colored true, and the value false if the vertex xi was colored false (this vertex cannot be colored red because it is adjacent to the red vertex). Every clause C must be true, because the piece of the graph used for C can only be colored with 3 colors if one or more of the vertices at the top is colored true. This means that the instance of Satisfiability is satisfiable.

This proves that 3-colorability is a NP complete Problem.