8. NP-Hard and NP-Complete Problems

the topic is NP hard and NP complete this is the most important topic and also this is the most confusing topic but I guarantee that I'll make these Concepts very much clear for you and one more thing don't watch this video if you are in a hurry watch it when you really prepared to watch this one when you're ready to watch this one okay let us start what this problem is see actually this topic is a research topic this is related to research so what is there for doing

research here first let us know about that see all the algorithms that we know or already we have learned I have written them here these are the algorithms which takes polinomial time and these are the algorithms which takes exponential time the problems for which we know the algorithms which take polinomial time like searching algorithm the problem is searching and the algorithms are linear search binary search this takes end time and this is login time and this n Square

for sorting and M sort is faster than that that is n login likewise zero na problem which takes 2 power n time and traveling sales person 2 power n all these are exponential they may be taking n into 2 power n or some is n power n some are but I just wrote them as 2 power n in common to show that are those are exponential now here we have categorized the algorithms into two one is polinomial time taking algorithms and exponential time taking algorithms what is the scope for doing

research here let us see see for searching we have a linear search algorithm which takes order of and time and faster than that is binary search which takes log and time we are in search of algorithm which is much faster than this one that is order of one time we want some searching algorithm it takes order of one time similarly the faster sorting algorithm takes order of n log and time and one of the Sorting is mer sort we want faster sorting algorithm that should take order of end

time faster than this one similarly for these exponential time algorithms we want polinomial time algorithms all these problems which are taking exponential time we want faster and easy method to solve them in just polinomial time because 2^ n or n^ n or 5 power n anything is much bigger than polinomial time even n^ 10 is smaller than 2 power n for some large values of n even n^ 100 is also smaller than 2^ n for some very large values of n so these are very time consuming algorithm so we

want polinomial time algorithm for this them this is the requirement and even for this also we want faster algorithms this is the requirement now this is a research area the person from Computer Sciences or from mathematics can solve these problems so people have been doing research on this one but there's no Solutions found so far yet for solving these problems in polinomial time then when the research work is going fruitless right we want something such that whatever the work we done should be

useful so there are guidelines or you can say framework made for doing research on these type of problems that is exponential type of problem and that framework is NP hard and NP complete or guidelines that is a part of framework is NP hard and NP complete so let us see what is the basic idea behind that so there are two points that I'm going to tell you based on this the entire based on these two points only I'll discuss them in very much detail but just I'm telling you those two points

right see first point when you are unable to solve these problems when you are unable to get a solution that is polinomial time algorithm for them then at least you do the work such that you try to show the similarities between them so that if one problem is solved all other problems should also be solved we will not be doing research work individually on each and every problem like I am trying to solve napsack problem and you are working on graph coloring we will not do it individually

let us combine them collectively and put some effort such that if one problem is solved all the problems should be solved so for that we have to show the relationship between them association between them to show that the properties they are having are similar so that if one is Sol the other can also Sol this is the first objective that try to relate the problem either solve it or at least relate it this is the first one second thing is when you are unable to write algorithms for them that is

deterministic why don't you write non-deterministic algorithms for them when you are unable to write polom time deterministic algorithm why don't you write polinomial time non- deterministic algorithms so what are these let us see so these are the two points I have shown you now I'll start with non-deterministic algorithms then I'll go to the relationship between them once we understand these two things everything is clear let us check let us talk about non-deterministic see the

algorithms that we write usually are deterministic so what does it mean each and every statement how it works we know it clearly we write the statements we are sure how they work so we know the working of the algorithm so that is a deterministic so we can write non- deterministic algorithm also yes that means we don't know how they are working working so how we can write algorithm which we don't know see if I am trying to write a 01 napsack problem that is polinomial time algorithm if I'm trying

to write then I may be knowing most of the statements but some of the statements that I may not be figuring out how to make them polinomial so leave them blanks leave them blanks and say this is non deterministic so when I come to know that how it has to be filled I will fill up that statements so in a non- deterministic algorithm also most of the statement may be deterministic but some of the statements are not deterministic so in this way what we can do is by writing non-deterministic

algorithm we can preserve our research work so that in future somebody else is working on this same problem he can make that non-deterministic part as deterministic this is the idea so suppose I have spent 10 12 years to solve this one of the type of problem but I want is unable to solve then what all the work that I have done should be preserved in some form so that is the idea behind writing non-deterministic algorithm so how do we write non- deterministic algorithm so here is an

example for non-deterministic search algorithm now I'll show you what are non-deterministic statements in this one this choice is nondeterministic success and failure these are the known statements that we use for writing non-deterministic algorithm so these statements are non-deterministic and we assume that all these statement takes just one unit of time we assume that these are taking order of one time now let me explain you the algorithm this is for searching a key from an an array of size

n let us check see if I just simply look at this algorithm without going into detail simply just see the statements it seems that the entire algorithm takes order of one time yes this is the constant time algorithm for searching see the fastest search method we know is binary search which takes login but this algorithm is taking order of one so really it is faster we need this one but this is non-deterministic let us see how this is working I'll explain from an array we have to search

for key so the first statement is what choice J so choice is called and it has given index J and what we do it is giving us the index of that key element it is saying that that key element is so ter of position J and we are checking is that key element is present at J if so then search is successful we'll write the output and search is successful if the key element is not there at that place means key element is not present in an array mean sear search is unsuccessful so we say

fail mean solution is not there mean key is not found it's not that it's unable to found it is able to find but the key is not present in an array so so simple now the the question is how this Choice came to know that the key element is present at jth index that's what it is non- deterministic once we come to know that we can find out the position of a key element in constant time then we'll fill up this line this is like a blank statement for us now once we fill up

this we have an algorithm which is taking order of one time this is how the algorithm non- deistic algorithm should look like see how this choice is working suppose I have an array of elements if I say key is nine and search then choice will give me directly index 4 how I don't know without checking anything without applying any search Logic directly it say at index force in constant time and how it can know that in constant time today we don't know maybe tomorrow we can find out a method

to directly get that answer that is the idea behind writing non-deterministic algorithm today tomorrow they may become deterministic by some other researcher I'm unable to do it maybe other person will be able to do my work is preserved this is the idea behind it see one more thing I will say that how this choice is working we don't know when we don't know how the things are working we call it as magic so this is magical now for us once we know how it is working it becomes a

technique right it becomes a logic so same way to today it's a magic for us so we have written like a magical algorithm tomorrow it will be procedural or it will be having its own logic so once we know that it becomes a deterministic and it will be taking constant time so like this we can write down non-deterministic algorithm for these polinomial time exponential time taking algorithms that is we will write down polinomial time algorithms this is polinomial time we'll

not write exponential again it's waste we will be writing non istic which is taking polinomial time for these type of problems which are right now taking exponential time so with this we Define two classes here let us see we Define p p is a set of those deterministic algorithms which are taking polinomial time example linear search binary search bubble sort merge sort single Source shortest path minimum cost spanning tree optimal merge pattern Huffman coding all

these takes polinomial time so all those algorithms which takes polinomial time and the algorithms are deterministic we call them as p and we have one more class of algorithm that is NP these algorithms are non-deterministic but they take polinomial time for whom we will try to write we actually we try to write for these type of problems these are exponential we convert them into polinomial but we don't know how it is possible so we leave the statements non- deterministic so algorithm becomes

non-deterministic so non-deterministic polinomial time taking algorithms so deterministic polinomial time taking algorithm and non-deterministic polinomial time taking algorithms so p and NP this is a famous diagram this is NP and this is p p is shown as subset of NP what doeses it mean the deterministic algorithms that we know today were the part of non-deterministic algorithm let us say mot for example we have found it recently in the past we were not knowing

it so it was non deterministic for us we were not knowing that there is a possible algorithm which takes an log and time we were working with bubble sort maybe so that was taking n Square time but recently we found out that M sort which is faster it's taking in log in time so that algorithm was non- deterministic and became deterministic now so this is the idea here so whatever the research work we do and we come up with some new algorithm we say that when we came to

know the algorithm that became deterministic so it once it was already there and that was non-deterministic for us right this is the idea set behind this one that is PN NP so today what all we know which are deterministic where yesterday they were non determin istic and today whichever is non- deterministic tomorrow that may become deterministic so we say that deterministic is a subset of non-deterministic and there is one more Cooks theorem here that try to Pro prove

that P is a subset of NB or P equal to NB that I'll come to it so for the guidelines of research work or the framework for research work I said that there are two things that are important so first thing I have completed that is writing non-deterministic polinomial time algorithms how to write and what is the meaning I have explained that one part I have finished now the second part I said that if you're unable to solve at least show the relationship between them

such that if one problem is solved it should be easy for solving other problems also in polinomial time we will not work on each and every problem individually so how to relate them together that is the next thing we will learn so for relating them together we need some problem as a base problem so which problem we take it as a base problem the base problem is satisfiability problem what is this this is a CNF formula that is propositional calculus formula using Boolean variables

let us say X1 X2 X3 I have three Boolean variables like x i are these then there is a Formula that is CNF formula is there example formula I'm taking that is X1 or X2 bar or X3 and X1 bar or X2 or X3 bar let us take this as an example formula this is CNF propositional calculus formula and it is having Clauses let us say C1 and C2 these are the Clauses and clauses are formed using disjunction and they are joined with conjunction so this is C F Formula now what is the satisfiability problem the

satisfiability problem is to find out for what values of XI this formula is true so what are the possible values of XI see X1 X2 X3 as these are Boolean so they can be zero or one so they can all be zero or this can be one or this can be 1 or these two are 1 0 0 1 0 1 1 1 0 11 1 so there are eight possibilities I should try all these eight possibilities and place them here and check for which of these values this is true and I should find out all possible values for which it is

true so how much time it will take for solving this one so how many values I should try 8 8 is what 2^ 3 so for n variables it will be 2^ n so this is also exponential time time taking problem this is 2^ n that is exponential time so this is similar to this they are also taking 2^ n or exponential so this is also taking exponential time so this belongs to the same category now these values even I can show them in the form of a state space tree I will prepare a state space

tree for this the solution for this problem I can say that X1 is 1 or X1 is 0 or X X2 is 1 or X2 is 0 or X2 is 1 or X2 is 0 there are three variables so X3 it can be 1 or 0 1 or 0 1 or 0 1 or zero now the paths from root to the leaf of these tree gives a solution like 1 0 1 this one if I take this this is 01 1 so this is showing all eight possible values of X1 x i X1 2 X3 so this is represented in the form of a state space St so this problem can also be represented in the form of a

state space tree now what we have to do we have to show that these are similar to this one such that if satisfi satisfiability is solved in polom time all can be solved in polinomial time or any one of them is solved then all of them can be solved in polinomial time so this is the idea we have to relate these problems so that we don't have to solve them individually if one is solved all are solved now how to prove that there are different methods for showing that

but to make it simple and understand I'll show you here only by taking 01 napsack problem by using this tree let me take an example of 01 naps problem here I have an example of 01 Absa problem there are three objects given for each object there is some profit and there's some weight and the capacity of the bag is eight we have to fill up the bag such that the profit is maximized and we should not exceed the capacity of the bag then to give the solution for the 01 appap problem I can write down

solution in the form of XI that is first value or second and third value can be either zero or 1 or 0 or 1 or 0 or 1 means all these values X1 X2 and X3 can be either 0 0 0 or 0 0 1 or 0 1 0 so how many possibilities are there 2^ 3 so it means for n objects it will be 2 power n so the solutions that are required for this one are similar to satisfiability problem how we solve satisfiability same way we have to try for 01 napsack then we have to see formula is true or not

here we have to see whether the profit is maximized or not so it means means this problem can also be solved using State space tree already you can check some video for 01 Absa problem I have drawn a state space tree so I will show one thing now I have removed both the problem there is no satisfiability formula there is no 01 Absa problem here now can you tell me this tree belongs to whom this tree is showing the solutions for satisfiability or 01 this is for both so this is how I

am relating them right there are differ there is a different method for relating okay that we will learn in next video you can watch it but here I'm relating like this so you can clearly see that if you can solve this one this state space St in polinomial time then means you can get the solution for this one also in polinomial and this one also in polinomial so that's how we show the relationship between these problems by taking this as a base problem now I will add this one also there in the

list satisfiability I also have included in this exponential time algorithms now we coin one term that is NP hard what is this I'll explain but let us call them simply as hard problem all these are hard problems right first of all let me call it as hard but satisfiability as we have taken it as a base problem so I'll say that is NP hard what does npl explain afterwards let us simply call it this is NP hard and this all I am saying heart problems they are taking

exponential time they are not NP heart then I was saying that we have to show that these are related to satisfiability only so that if that is solved all can be solved now how to show the relationship is the procedure is

reduction so what this reduction is we take let us says example satisfiability problem and we take one of the problem for example 01 absct problem and we say that satisfiable reduces to 01 Absa problem what does it mean what we show we show that we take some instance of satisfiability that is one formula we take and that formula from that formula will convert into a 01 aback problem we take an example of satisfiability problem and we convert that problem into 01 AB problem and we

say that if this 01 ABS problem can be solved in polinomial time and that same algorithm can be used for solving this also in polinomial time so that's how it means if this is Sol that can be solved if that is solved this can be solved if some algorithm is solving this one in polinomial time then same algorithm can solve this one also in polinomial time now who is solved first that is a different thing but this how we show that that they are related to one another anyone you solve all the

other one will also be automatically solved so how we show the relationship we take an example formula and that formula will convert into 01 abside problem and this conversion for conversion we will not take much time we take polinomial time only we take polinomial time we don't take exponential conversion itself is taking exponential time then it's of no use so conversion will be done in polinomial time this is one important thing next I said that this is NP hard let us call it as NP

hard satisfiability is NP hard this is NP hard right if satisfiability is reducing to 01 napack problem then this also becomes NP hard now this problem comes into the class of NP hard this means that if you sol anyone the other one automatically get Sol so means we have proed the relationship between them so if you are showing that satisfi reduces to some problem L then if it is proved then this also becomes NP hard this also becomes NB hard and one more thing this

reduction has a transitive property if satisfiability is reducing to L1 then L1 is also NP hard and if L1 is reducing to L2 then L2 also becomes NP hard means if I have shown 01 is reduced by satisfiability then I can show graph coloring reduced by 01 or some of the subset reduced by graph coloring or hamiltonian is reduced by graph coloring I can show it like this so you don't have to bring all of them onto satisfiability only you can show others one any one of the problem related to

that right either satisfiability or 01 so this is NP hard if satisfi reduces to any problem that that problem also becomes NP hard now one more important thing satisfiability if it is reducing to some problem then that problem is also becoming NP hard so this is one thing that is showing relationship and one more thing we were doing that we were writing non deterministic algorithms so do we have a non-deterministic algorithm for any of this problem yes one of the problem that

is we know it is proved it is there that is satisfiability problem for this we have a non-deterministic polinomial Time algorithm it's existing it's existing so satisfiability is NP hard as well as this is NP complete is NP complete if an problem is having non-deterministic time algorithm then that problem also becomes NP complete so satisfiability is a known NP complete problem so for any of these problems if this problem is reduced by satisfiability so this is NP hard this

is NP hard and if you write a non-deterministic polinomial time for Al algorithm for this one then this also becomes NP complete NP complete so for doing research work on any problem of your problem then you have to do two things one you have to show that this is directly or indirectly related to satisfiability and you should write a non-deterministic algorithm for your problem if you complete the first part that is shown that it is reduced by satisfiability then your problem became

a part of NP heart class and if you have also written a non-determinate IC algorithm then your problem has reached in a class called NP complete means you have completed the research work basic required research work if you are able to directly solve that problem okay solve it whether go well and good if not at least you should do this then your research work is completed now I will draw one more well-known diagram this is a set of NP hard problems who is is there in this one

satisfiability then if you prove any of these problem that is reduced by S satisfiability let us say 01 it also becomes a NP hard if you prove graph coloring then that is also NP hard if you are proving that they are directly or indirectly reduced by satisfiability they will become NP they are coming into NP heart this is one part we have to do as a part of research then the second part we should also write nondeterministic algorithm NP NP this is another thing writing

non-deterministic algorithm do you have a non-deterministic algorithm for satisfiability yes so this is in NP hard only but this is in this intersection area so this is also NP hard as well as this is having non-deterministic polinomial time algorithm so what is this area called as this is NP

complete this is NP complete intersection of NP hard and nistic algorithms that's all the major part we have completed then one more thing we have drawn already that is p was also there this was another discussion we did that P is the things that we are deterministic today and NPS that is non deterministic and tomorrow we may be knowing those non- determinists also that will be coming inside p and we believe that this P will be keep on expanding right this will be keep on

growing the P will become bigger and bigger so that non-deterministic will be becoming deterministic right so we believe like this our Circle of Knowledge will be going on growing that's how we believe now how much it is we don't know so it will be going on growing and we believe that at some stage it will go and become equal to NP means everything that is not known we will be knowing it right that is the idea one major problem remaining the thought that we have that today we are writing

non-deterministic believing that tomorrow that will become deterministic is it perfect do you think it's really going to work if it fails we never found out that then all our research work is waste so for that we need to to prove that really tomorrow we may be knowing non-deterministic algorithm and they will be converted into polinomial time DET domistic algorithms right so we have to at least prove that yes what we are doing is right so for that if we are able to

prove that P is equals to NP we are able to prove that P is equal to NP then it is proved that whatever the non- deterministic we are writing tomorrow that may become deterministic so for that we say that P is a subset of NP we don't know how much this is so that's why we write equal also then we have to prove p is equals to NP whether p is equal to NP or not see if you are proving p is equal to NP means it's existing but you don't know right it is existing you don't have

to you don't have to do research and find out or invent it it's existing Discover it so when you say p is equals to NP so what is non deterministic for you it's existing just you discover it that is the meaning so if you are able to prove this then what all the work that we are doing research work that's going to be successful that is the idea in this one so cook has tried to prove that so there is a famous theorem on this one Cook's theorem he has tried to prove that he proved this one that if

satisfiability is lying in P so it means where this p is we don't know even P can be in the intersection part of this one right so he said that satisfiability is in P if and only if p is equals to NP satisfiability will come into P if and only if p is equals to NP means satisfiability will become deterministic if p is equals to NP he said that this P can be proved as correct if you prove that satisfiability is in P he did not prove it he said that somebody proves

this one then our work is correct our work is perfect so this is all the discussion behind NP hard and NP complete problems so that's all about this one so I'll may be I may be making one more video for solving some NP hard graph problems right so leave a comment for this video let me know how much you have understood