5.2 Satisfiability , NP hard and NP complete

hello guys we are back with our next lecture in this lecture let us go through satisfiability first we will be going through satisfiability then we will be going to reduction after that we will be going through np hard and np complete definitions guys these three these three four topics are really important guys because these three four topics will be given as even as la queues in some kind of examinations so please make sure that you are perfect with the concepts so i'll be giving you an overview guys because i'm also i also didn't find much theory or much explanation about these concepts so i'll also give you an introduction for them so that you can refer a textbook or somewhere and you can write it on your own okay so basically satisfiability satisfiability is nothing but when you are solving a particular problem okay if you are solving one more problem so if these two problems are having some similarities if this problem is solved indirectly this problem is also solved with the help of this solution right so this concept is also called as reduction also we'll be using this exact concept and in satisfiability we'll be comparing them guys okay so basically satisfiability can be represented in two ways that is nothing but cnf and dnf but basically we will be using cnf to represent them in this chapter okay that is nothing but conjunctive normal form so conjecture normal form is nothing but in between we will be having or operation and in between these or operation elements will be having and operations okay so if you take the possible combinations that is nothing but x1 x2 x3 so we can say that how many ways can you represent the combinations guys so i'll be asking you a simple question how many ways can you represent a combination so i'll be just explaining you with the help of these combinations only i'll be establishing a relation between boolean algebra like zeros ones and zeros once like you will be writing in truth tables right so with this i'll be establishing a relation with the state space tree guys in which we discussed in our previous chapter state space tree okay so i hope now you are thinking that okay how can i do it so basically we all know that for three elements that is x1 x2 x3 we are having 8 combinations that is nothing but 2 power 3 that is 8 so 2 power n so we are having eight combinations so i have just listed them out here so zero zero zero one one zero one one zero zero zero one one zero one one top four zero stop four below four once okay okay so now for this i will be constructing a state base tree so if you assume here each path is having a particular flow so that is what these all eight elements are so that is nothing but initially among x one i will be selecting one and zero okay at x2 here i will be selecting one and zero and here also i'll be selecting one and zero so now we are done with four parts whereas at the end i will be selecting two two two two at the end we have reached the eight different parts the exact path of this so indirectly we have established the relation between these two so now if one problem is solved the other will also be solved so that is the main logic behind this so you need to find some similarities between them and you will be trying to solve one and you can solve anything so for the above cnf and also for snap sac and there are many other possibility algorithms guys for these things we for state-based diagrams we have drawn for multiple algorithms in our previous chapter right okay so the we can say that if the satisfiability problem is solved in polynomial time using same concept we can solve other related problems too okay so basically if one problem is solved with the help of satisfiability that is nothing but the state space tree or any kind of boolean algebra or any kind of method using it if you solve it in polynomial time then all the algorithms which belongs to that kind of sector will all be solved guys okay so this whole process of satisfaction satisfiability which i have just told you will be considered considered in deduction so basically deriving deriving from one to another so basically if i say the first algorithm is really hard so based if something is based on the first algorithm like it is almost similar then indirectly this algorithm is also tough right indirectly for students right yes so similarly here also will be deriving one from the another so satisfiability is directly proportional to the zero by one knapsack so we are assuming both are equal in some instance so that is the reason why i wrote instance instance one instance two if it is solved in polynomial time then this can also be solved in the polynomial time so basically i hope everyone knows that the satisfiability problem will lie in between the np okay i'll be just showing you the graph so that will be clear so it will be become it will be in between np and np hard okay so here we will be having the satisfiability problem that is the reason why the satisfiability problem comes under np complete so this component or interior or intersection will be the complete np complete okay so you can also say that satisfiability belongs to np hence we can say that zero by one also belongs to knapsack sorry zero by one also belongs to np hard but satisfiability also belongs to np complete as it is non-deterministic algorithm because there is no solution for it just you will be assuming that okay by doing this this this you'll be getting the answer that's it so that is the reason why this also comes under non-deterministic so hence you can draw a small graph like this so now we'll be discussing about the concept of np hard and np complete definitions guys so basically np heart an algorithm which follows or can be solved by basics of satisfiability or any other instance similarly then it can come under np hard so if you remember i pushed np into np hard that is nothing but zero by one knapsack because in our previous example we have we assumed that both are equal and if one is solved the other is also solved so indirectly you can say that zero by one knapsack also belongs to np heart okay so now your question will be np complete so if it has a non-deterministic polynomial time algorithm so now you know that zero by one asset belongs to npr so now you start writing the non-deterministic algorithm for this so if you write non-deterministic algorithm it will move to here if you convert that determine non-deterministic algorithm into deterministic it will conv it will push into polynomial polynomial time okay so that is the main concept behind p np and inside np we are having two those are nothing but np hard and np complete okay so now we are done with the introduction part of this chapter guys so in the next lecture we will be going through cook's theorem okay so cooks stated that we can say that polynomial time and non-polynomial time are both equal so that is what he has stated guys so we'll be discussing some kind of introduction of the theorem because i i didn't find the theorem the exact theorem i didn't find anywhere so i will be just introducing the theorem and we will will be as we'll be going through some assumptions okay so in the next lecture we'll be continuing with cook's theorem thank you thanks for watching

Channel: OU Education

Views: 16,387

Keywords: ou education, ou, education, education4fun

Id: U_Od3y932X0

Length: 7min 30sec (450 seconds)

Published: Mon Nov 16 2020