In This section lets understand the Basic concept of NP Hard & NP Complete Algorithm
NP-Hard and NP-Complete Problems
An algorithm A is of polynomial complexity is there exist a polynomial p( ) such that the computing time of A is O(p(n)).
Definition: P is a set of all decision problems solvable by a deterministic algorithm in polynomial time. NP is the set of all decision problems solvable by a nondeterministic algorithm in polynomial time.
P NP
The most famous unsolved problem in Computer Science is whether P=NP or P ≠ NP =>P =NP(?)
Cook’s theorem: Satisfiability is in P if P = NP
For many of the problems we know and study, the best algorithms for their solution have computing times can be clustered into two groups-
1. Solutions are bounded by the polynomial
2. Solutions are bounded by a nonpolynomial
No one has been able to device an algorithm which is bounded by the polynomial of small degree for the problems belonging to the second group.
The theory of the NP-Completeness does not provide any method of obtaining polynomial time algorithms for the problems of the second group.
“Many of the problems for which there is no polynomial time algorithm available are
computationally related”.
Two classes
1. NP-Complete– have the property that it can be solved in polynomial time if all other NP-Complete problems can be solved in polynomial time.
2. NP-Hard- if it can be solved in polynomial time then all NP-Complete can be solved in polynomial time.
“All NP-Complete problems are NP-Hard but not all NPHard problems are not NP-Complete.”
NP-Complete problems are subclass of NP-Hard
