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 will make these concepts very much clearer for you and one more thing don't watch this video if you are in hurry watch it when you are really prepared to watch this one when you are ready to watch this one ok let us start what this problem is see actually this topic is a research topic and 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 polynomial time and these are the algorithms which takes exponential time the problems for which we know the algorithms which take polynomial time like searching algorithm the problem is searching and the algorithms are linear search binary search this takes n time and this is login time and this n square for sorting and merge sort is faster than that that is n log n likewise 0 knapsack problem which takes 2 power n time and traveling salesperson to Warren all these are exponential they may be taking any 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 door those are exponential now here we have categorized the algorithms into two one is polynomial 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 n time and faster than that is a binary search which takes log n time we are in search of algorithm which is much faster than this one that is order of 1 time we want some searching algorithm we take for a fun time similarly the fastest sorting algorithm takes order of n log N and one of the sorting is Mirsad we want faster sorting algorithm that should take order of end time faster than this one similarly for these exponential time algorithms we want polynomial time algorithms all these problems which are taking exponential time we want faster and easy method to solve them in just polynomial time because to power N or n power n or v power and anything is much bigger than polynomial time even any power 10 is smaller than 2 power n for some large values of n even n power hundred is also smaller than 2 power n for some very large values of n so these are very time-consuming algorithm so we want polynomial time algorithm for 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 is no solutions found so far yet for solving these problems in polynomial time then when the research work is going fruitless right we want something such that whatever the work be done should be useful so there are guidelines or see we can say framework made for doing research on these type of problems that is exponential type of problem and that framework is and be hardened and be complete or guidelines that is a part of framework is NP hardness be complete so let us see what is the basic idea behind that so there are two points that I am going to tell you based on this the entire topic is based on these two points only I'll discuss them in very much detail but just I am 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 polynomial 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 so all other problems should also be solved we will not be doing research work individually on each and every problem like I am just trying to solve a knapsack 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 solved the other can also solve this is the first objective that try to relate the problem either solve it or at least related this is first one second thing is when you are unable to write algorithms for them that is a deterministic why don't you write non deterministic algorithms for them when you are unable to write polynomial time deterministic algorithm why don't you write polynomial time non deterministic algorithms so what are these let us see so these are the two points I have shown you now I will start with non deterministic algorithms then I'll go to the relationship between them once you 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 so how we can write algorithm which we don't know see if I am trying to write a zero of knapsack problem that is polynomial time algorithm I found a 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 polynomial 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 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 n2a years to solve this one of the type of problem but I wanna save 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 you write non-deterministic algorithm so here is an example for non-deterministic search algorithm now I will show you what our non-deterministic statements in this one this choice is non-deterministic success and failure these are the known statements that we use for writing non deterministic algorithms so these statements are non-deterministic and we assume that all these statement takes just one unit of time we assume that these are not taking order of one time now let me explain with algorithm this is for searching a key from an an array of size and now let us check see if I just simply look at this algorithm without going into details simply see the statements it seems that the entire algorithm takes order off one time yes this is the constant time algorithm for searching see the fastest search method we know is binary search which takes log in 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 will 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 and so position J and we are checking is that key element is present at J if so then search is successful will write down put am such a successful if the key element is not there at that placements the key element not present in an array when such a search is unsuccessful so we say failed when solution is not there when scheme is not found it's not that it's unable to form it is able to find but the key is not present in an area so so simple now the question is how this choice came to known that the key element is present at g8 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 you fill up this we have an algorithm which is taking order of one time this is how the algorithm non-deterministic algorithm should look like see how this choice is working suppose I have an array of elements if I say keys 9 and search then choice will give me directly index 4 how I don't know without shaking anything without applying any search logic directly it says at index fours 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 am 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 for King 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 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 our deterministic and it will be taking constant time so like this we can write down non-deterministic algorithm for these polynomial time exponential time taking algorithms that is we will write on polynomial time algorithms this is polynomial time not right exponential again it's waste we will be writing non-deterministic which is taking polynomial time for these type of problems which are right now taking exponential time so with this we define two classes here let us see verifying P P is a set of those deterministic algorithms which are taking polynomial 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 polynomial time so all those algorithms which takes polynomial 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 polynomial 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 polynomial but we don't know how it is possible so we leave the statements non deterministic so algorithm becomes non deterministic so non deterministic polynomial time taking algorithms so deterministic polynomial time taking algorithm and non deterministic polynomial time taking algorithms so P n NP this is famous diagram this is n P and this is P P is shown as subset of NP what does it mean the deterministic algorithms that we know today where the part of non-deterministic algorithm let us say merge sort 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 in log n time we were working in bubble sort maybe so that was taking n square time but recently we found out that more sort which is faster it's taking in log n 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 means it was already there and that was non-deterministic for us right this is the idea set behind this one that is P and NP so today what all we know which are deterministic where yesterday they were non-deterministic and today whichever is non-deterministic tomorrow that will become deterministic so we say that deterministic is a subset of non-deterministic and there is one more cooks theorem here that try to prove that p is a subset of NB or p equal to NP that I will 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 polynomial 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 are 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 polynomial 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 brains problem is satisfiability problem what is this this is CNF formula that is propositional calculus formula using boolean variables let us say x1 x2 x3 I have three boolean variables like x ir DS then there is a formula that is CNF formula is their example formula am 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 CLS propositional calculus formula and it is having clauses let us say C 1 and C 2 these are the clauses and clauses are formed using disjunction and they are joined with congestion so this is CNF formula now what is this satisfiability problem the satisfiability problem is to find out for what values of x i this formula is true so what are the possible values of x I see x1 x2 x3 as these are boolean so they can be 0 or 1 so they can all be 0 or this can be 1 or this can be 1 or these two are 1 0 0 1 0 1 1 1 0 1 1 1 so there are 8 possibilities I should try all these 8 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 power 3 so 4 n variables it will be 2 power and so this is also exponential time taking problem this is 2 power n that is exponential time so this is similar to this they are also taking 2 power 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 a solution for this problem I can say that X 1 is 1 or X 1 is 0 or X 2 is 1 or X 2 is 0 or X 2 is 1 or X 2 is 0 there are 3 variables so X 3 it can be 1 or 0 1 or 0 1 or 0 1 or 0 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 0 1 1 so this is showing all eight possible values of x1 X I X 1 2 X 3 so this is represented in the form of a state space tree 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 satisfied satisfiability solved in polynomial time all can be solved in polynomial time or any one of them is solved then all of them can be solved in polynomial 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 will show you here only by taking zero-one knapsack problem by using this tree let me take an example of zero a knapsack problem here I have an example of zero a knapsack problem there are three objects given for each object there is some profit and there is 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 back then to give the solution for the zero of a knapsack problem I can write down solution in the form of X I that is first value or second and third value can be either 0 or 1 or 0 or 1 or 0 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 to power tree so it means for n objects it will be 2 more 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 zero-one knapsack daley have to see formula is true or not here we have to see whether the profit is maximized or not so it means this problem can also be solved using state space tree orderly you can check some video for 0 and knapsack 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 for there is no suitable knapsack problem here now can you tell me this tree belongs to whom this tree is showing the solutions for satisfiability or zero one this is for booth so this is how I am relating them right there are defects there is a different method for relating okay that we will learn in the next video you can watch it but here I am relating like this so you can clearly see that if you can solve this one this state space tree in polynomial time then means you can get the solution for this one also in polynomial and this one also in polynomial 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 I have included in this exponential time algorithms now we coined one down that is np-hard what is this I'll explain but let us call them simply as hard problem all these are hard problems but first of all let me call it as hard but satisfiability as we have taken it as a base problem so I will 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 hard problems they are taking exponential time they are not np-hard then I was saying that we have to show that these are related to satisfiability only so that is that is all all can be solved now how to show the relationship is the procedure is reduction so what this reduction is we take let us say example satisfiability problem and we take one of the problem for example zero-one knapsack problem and we say that satisfiability reduces to zero a knapsack problem what does it mean what we saw 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 zero-one knapsack problem we take an example of satisfiability problem and convert that problem into zero and have sat on them and we say that if this 0 a knapsack problem can be solved in polynomial time and that same algorithm can be used for solving this also in polynomial time so that's how it means if this is solved that can be solved if that is solved this can be solved if some algorithm is solving this one in polynomial time then same algorithm can solve this one also in polynomial time now who is solved first that is a different thing but this how we show 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 zero on that sub problem and this conversion for conversion we will not take much time we take polynomial time only we take polynomial time we don't take exponential conversion itself is taking exponential time then it's of no use so conversion will be done in polynomial time this is one important thing next I said that this is np-hard let us call it as and be hard satisfiable it is np-hard this is np-hard right if satisfiability is ready using two zero one knapsack problem then this also becomes np-hard now this problem comes into the class of np-hard this means that if you solve any one the other one automatically gets solved so means we have proved the relationship between them so if you are showing that satisfiability radius to some problem L then if it is proved then this also becomes np-hard this also becomes np-hard and one more thing this reduction has a transitive property if satisfiability is reducing to l1 then l1 is also in Bihar and if l1 is reducing to l2 then l2 also becomes np-hard means if I have shown 0 1 is reduced by a satisfiability then I can show graph coloring reduce zero-one are some of the subsets 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 on to satisfiability only you can show others one any one of the problem related to that right either satisfiability or zero one so this is np-hard if satisfiability 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 and be 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 polynomial time algorithm its existing it's existing so satisfiability is np-hard as well as this is NP complete this np-complete if any 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 a satisfiability so this is np-hard this is np-hard and if you write a non-deterministic polynomial time for Al Gore algorithm for this one then this also becomes np-complete np-complete so for doing research walk on any problem of your problem then you have to do two things one you have to show that this is a 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 reducible satisfiability then your problem became a part of np-hard class and if you have also written a non-deterministic algorithm then your problem has reached in a class called and be complete means you have completed the research work basic required research work if you are able to directly solve that problem okay solve it's rather good well and good if not at least you should do this then your research work is completed now I will draw one more Valon diagram this is set off np-hard problems who is there in this one satisfiability then if you prove any of these problem that is reduced by sub satisfiability let us say 0 1 it also becomes a and B hard if you prove graph coloring then that is also and be hard if you are proving that they are directly or indirectly reduce by satisfiability they will become np-hard they are coming into np-hard this is one part we have to do as a part of research then the second part we should also write non-deterministic algorithm and b NP does not other thing writing non-deterministic algorithm do you have a non deterministic algorithm for satisfiability yes so this is an np-hard only but this is in this intersection area so this also np-hard as well as this is having non-deterministic polynomial time algorithm so what is this area called as this is np-complete this will be complete intersection of np-hard and non deterministic algorithms that's all the major part we have completed then one more thing we have drawn already that is P 1 also there this was our another discussion we did that P is of the things that we are deterministic today and anything is that is non-deterministic and tomorrow we may be knowing those non-deterministic so 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 something 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 and be once 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 find out that then all our research work is waste so for that we need to prove that really tomorrow we may be knowing non-deterministic algorithm and they will be converted into polynomial time deterministic 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 and B 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 dis you don't have to do research and find out or invent it its existing discover it so when you say P is equals to NP so what is non-deterministic for you its existing just you discover it that is the meaning so if you are able to prove just then what all the work that we are doing research for that's going to be successful that is the idea and this so cook has tried to prove that so there is a famous theorem on this one gooks theorem he has tried to prove that he proved this one that if satisfiability is lying in p so it means we're the species 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 equal to NP satisfiability will come into P if and only if P is equals to n P means satisfiability will become deterministic if P is equals to n P he said that this poor 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 and be harder than P complete problems so that's all about this one soil maybe I may be making one more video for solving some NP hard graft problems right so leave a comment for this video let me know how much you have understood

Channel: Abdul Bari

Views: 1,243,314

Keywords: algorithms, algorithm, NP-Hard problems, NP-Hard and NP-Complete problems, NP-Hard and NP-Complete, np hard and np complete problems, np hard and np complete, abdul bari, bari, gate

Id: e2cF8a5aAhE

Length: 31min 53sec (1913 seconds)

Published: Wed Feb 28 2018