NP-Hard and NP-Complete classes
A problem is considered to be in NPC, that is NP-complete class, if it is a part of NP, and is as tough as any other problem in NP. And, a problem is considered to be NP-hard if all the problems in NP can be reduced in polynomial time. If a problem can be solved in polynomial time and is in NP, it means they have a polynomial time complexity.
These types of problems are referred to as NP-complete problems.
The NP-complete phenomenon is important for theoretical and practical purposes.
How to define NP-completeness?
To be NP-complete it must fulfill the following criteria:
- The language must be in NP.
- It must be polynomial-time reducible.
If the language fails to satisfy the first criteria but fulfills the second one it is considered to be NP-hard. The NP-hard problem cannot be solved in polynomial time. But, if a problem is proved to be NPC, we do not focus on finding the most efficient algorithm for it, instead, we focus on designing an approximation algorithm.
Some examples of NP-complete problems are as follows:
- To determine if a graph has a Hamiltonian cycle.
- To determine if a boolean formula is satisfactory.
Some examples of NP-hard problems are as follows:
- The traveling salesperson problem or TSP.
- Set cover problem
- The circuit satisfiability problem.
- Vertex cover problem.
Why do we consider the traveling salesperson problem is NP-complete?
To understand why we consider TSP as NP-complete we must first know what the traveling salesperson problem is.
In the traveling salesperson problem, we have a salesperson who has a list of cities to visit, exactly once, and must end at the source where he started his journey from.
Proof:
For TSP to be NP-complete it must fulfill the criteria we discussed above, so we start by proving that TSP belongs to NP. In the TSP problem we check if the tour of the listed cities contains each vertex once. Then we calculate the total cost of the edges of the tour. In the end, we decide which tour has the least cost and can be completed in polynomial time. Therefore, we can conclude that TSP belongs to NP.
The second criterion is to prove that TSP is NP-hard, we do this by showing that the Hamiltonian cycle is less than or equal to TSP, as we already know that the Hamiltonian cycle is NP-Hard.
We assume a graph, that has G= (V, E).
Let G be the graph for the Hamiltonian cycle.
We construct an instance of TSP, the graph for which is denoted by: G’= (V’, E’).
Let us suppose the Hamiltonian cycle h, exists in G. It implies that the cost of each edge is zero, in G’, and each edge belongs to E. Therefore, h also has a cost of 0 in G’. So if the graph of the Hamiltonian cycle G has a cost of 0, then graph G’for TSP, also has a total tour cost of zero.
And vice versa.
Hence, we can conclude that TSP is NP-hard, and hence NP-complete.
Reference
NP-Hard and NP-Complete classes