NP Hard and NP Complete Problem
Polynomial Time Algorithms are the algorithms that takes polynomial time, that is the problem for which we know the algorithm which takes some particular polynomial time while, Exponential Time Algorithms are the algorithm whose time is known polynomial. 2^n time is far more larger compared to polynomial time.
Here in Polynomial Time Algorithms merge sort is the sorting technique that occupy n*logn time which is faster compared to other techniques but still we need and algorithm that is way more faster than this algorithm that is O(1).
We want that exponential time algorithms must take polynomial time.SO one can say that particular framework is there to solve Exponential Time Algorithms in Polynomial Time that is NP Hard or NP Complete.
Now, how can we do that?
As, one cannot find the exponential algorithm in polynomial time then ,what we need to do is ..
1> we must try to find out the similarities between all the exponential algorithms such that if one of the problem is solved all other problems are also solved of exponential type.So Either solve it or relate it by associating the one Exponential Problem with another.
2>When one cant able to write polynomial Deterministic Problem the do write Non-Deterministic problem
What is Deterministic and Non-Deterministic ?
when one is knowing the working of each and every statement ,how it works what is the meaning of it, what is the mechanism of that algorithm then that is called Deterministic
When one is not knowing the working of the algorithm then it is known as Non-Deterministic. In such algorithm there can me most of the deterministic statements too but not all.It is Reserved for future so that someone can determine it and make it deterministic.
For e.g.:
Algo NSearch(A,n,Key)
{
J=choice(); // non deterministic — 1 unit time
If(key=A[j] ){
Write(j);
Success();// non deterministic — 1 unit time
}
Write(0);
Failure(); // non deterministic — 1 unit time
}
As in this Non Deterministic Algorithm complexity is O(1)
We assume that all non deterministic statements take 1 unit of time.Entire time taken is 0(1) time. This is way faster than normal search but it is non deterministic ultimately.Once we come to know that what is mechanism in this functions than this will become deterministic but right now we are not having any idea about it so its obviously non deterministic
What is P and NP ?
P is set of deterministic algorithms ,taking polynomial time. Ex: Huffman coding, MST
NP is Non deterministic but Polynomial time taking algorithm
Figure represents P is the Subset of NP which says that, before all the algorithms were non deterministic algorithms but after passing of moments all those became deterministic
As there are many Exponential algorithms , and according to the rule that is if one cannot find the exponential algorithm in polynomial time then ,what we we must try to find out the similarities between all the exponential algorithms such that if one of the problem is solved all other problems are also solved of exponential type. So For creating that relation we need to take a Algorithm
CNF Satisfiability
Xi={ x1,x2,x3}
CNF Formula =(x1 v x2 v x3) ^ ( (-x1) v x2 v (-x3))
Clause c1 = (x1 v x2 v x3) and Clause c2 = (x1 v x2 v x3)
Satisfiability says that to find out for what values of xi this c1 and c2 can be true so possibilities are:
So how many time it will take = 2³ as there is x1 ,x2 ,x3= 8 possibilities
For n vertex = (2^n) . It is also taking exponential time algorithm
Now by placing all the possibilities we need to see which of the possible is true
So will generate STATE SPACE TREE for that:
This shows all possibilities. Now we have to relate all the exponential problem with this problem.
Example: 0/1 Knapsack Problem
{ 0/1, 0/1, 0/1} = 000 001 010….. and so on 8 possibilities for x1, x2, x3
What is Np-HARD and What is NP complete ???
All exponential problems are hard problems. But as Satisfiability we took it as Base Problem so will consider it as NP hard problem. Now here we have to relate the other exponential problem with Satisfiability. And that procedure is Reduction.
Sat tendsto 0/1 knapsack where, satsifiabilty reduces o/1 knapsack problem
I1 tendsto I2
Take sat as base and convert into knap I1 and I2 areinstance if sat. If I1 is solved in polynomial time then I2 that is , 0/1 also can be solved such way they are related to one another where Conversion also take polynomial time.Now so 0/1 also becomes Np Hard because that is
if Sat tendsto L then, l also become NP Hard
if L tendsto L1 and L1 tendsto L2 then, L1 and L2 also becomes NP hard
Satisfiability is reducing some problem among exponential problem then that problem also becomes NP hard which shows shows Relationship.
Satisfiability having Nondeterministic algorithm written and also NP Hard it is then is called NP –complete. NP –complete is deterministic+NP Hard
If sat tendsto L then sat is NP hard and NP complete as well while L is NP hard but if for that : if in future someone writes Nondetermistic algorithm then it will become NP complete.
P keeps on increasing.
If p=np
Then it is proved what ever non deterministic we are writing that means it will become determinstic.Even p can be at intersecting point.
This is what NP Hard and NP Complete Problem is..
Lets see how NP Hard is converted into NP Complete BY using an example of Clique Decicion Graph Problem…
As we know that a vertexes joining all the vertex using edges.The above mention figure also consiste of 3 Complete Graphs whose all the vertexes are connected by edges where
Vertex=n, edges =n(n-1)/2
What is Clique?
Clique is subgraph of a graph which is complete.
But by conserving 3 vertex , It is complete .
Lets check the exact meaning of the Clique Decision Graph Problem
Here there is are cliques like k=4 (1,2,3,4), k=3(3,5,6) and k=2( for many) but k=4 is max so clique = 4
As Clique is a decision problems lets check what is Decision problem and what is Optimization problem? Decision prob is, If problem require answer in true or false is decision like , Is there clique of 3 in the given graph or not? while,, What is max clique in graph? is optimization like finding max or min cliques from the graph
Rules how to connect the edges of the graph:
1> Should not connect vertexes belong to same clause
2> And cant connect vertex with the negation of the vertex
Note:Red one cant be connected according to the rules
Clique decision graph problem is NP Hard
P= l1
L1 tends to L2
I1 tends to I2
Conversion in polynomial problem using Satisfiability
Sat tends to clique decision problem
I1 tends to I2
Sat is known np hard and lets prove cdp also np hard
lets take 3 variable: x1 x2 x2
F= ( x1 v x2) ^ ((-x1) v (-x2)) ^ (x1 v x3)
C represents clause 1 2 3,where c1=( x1 v x2), c2=(-x1) v (-x2) and c3 =( x1 v x3) where(-x1 and -x2 are x1 and x2 bar)
K= clique is there of max= 3 as formula having 3 clauses. If , k clause then k size clique would be there
There are several steps to compare satisfiability and clique decision problem
1> Select vertex(a pair) and then create a table based on the veterx where 0 or 1
For (-x1)v x2 v x3
0 represent bar that is, if (-x1) then value would be 0
2> Now compare it with the formula created
F= ( x1 v x2) ^ ((-x1) v (-x2)) ^ (x1 v x3)
As x1=0, x2=1(according to table), 0 v 1=1 , where v represents Oring
( x1 v x2)= 0 v 1=1 =c1
((-x1) v (-x2))=1 v 0 = 1= c2
(x1 v x3)=0 v 1=c3
c1=1 ,
c2=1 ,
c3=1 so for that particular vertexes
Such way we can say that,if satisfiability is NP hard then CPD is also np hard, as both are been related to each other which is been shown.
