P NP NP-Hard NP-Complete||Design and Analysis of Algorithm || English ||By Studies Studio

P NP NP-Hard NP-Complete||Design and Analysis of Algorithm || English ||By Studies Studio


Hi ! welcome back. I am Rakesh Nayak. Today we are going to discuss about P NP and NP hard and NP Complte Problem. Before we
start just one small request, if you are a new visitor, kindly subscribe it and
press the bell icon so that you will get all the updates from this channel. Let us
start.. Basically any problem is given to find the solution of an algorithm and the algorithm can be solved either in polynomial time or in a non polynomial
time, that we already know. Now let us see what is a P class problem. P class
problems are those problems which can be solved by polynomial time. For example, if
you say the sorting and searching algorithms are polynomial time. Why you
can say if you take a searching algorithms to take linear search, the
complexity is order of N, O(N) and if you are searching using binary search
it can be log base 2(N). Similarly for sorting also we can sort a set of data
in a polynomial time. Now let us see what is NP class problem. NP class problem are those problems which cannot be solved using polynomial time but can be
verified in polynomial time. For example, if you are having a SU-DO-KU problem,
prime factor problem, scheduling problem, traveling salesmen problem.. all these
problems are examples, there are many more in this class. You might have
realized the polynomial time with sorting and searching but I’m going to
give an example of SU-DO-KU right now. how that I can say that this is a NP
class problem. Let us see. Let us say this is a SU-DO-KU.It means in all
the boxes we have to fill the data from 0 to 9 in all the rows the data must be
0 to 9 in all the column the data must be 0 to 9 and none
of other places numbers will be repeated Let us try to solve the first 3 X 3
matrix. So 1 2 4 & 7 are missing in this first block. Let us try to fill the first
empty square. I can fill it with, out of the 4, in one way. It means four possibilities
are there to fill one square. For the next square there will be three possibilities. For the next square
I’ll be having two possibilities and for the last square I’ll be having only one
possibility. It makes 1 into 2 into 3 into 4, to fill
this 3 cross 3 matrix I will be having 4! ways I can fill it. There are 9 such matrixes are there. And in each of the matrix number of unknowns are not
fixed. Here there are 4 unknowns, here there are 5 unknowns, here there are
8 unknowns that I have to fill. Along with that I have to check, in the first
row how many unknowns are there. it must suit or it must fit in such a
way that whatever value and keep it here that value should not appear in this
column or in this square. So it is very very difficult, we take exponential time to solve this problem. If somebody has solved the
problem and told me that I have the solution for this SU-DO-KU, then I can
very well verify in this Square 1 to 9 is there or not. In this row is there any
repetition, in this column is there an repetition, So I can very well check or
I can very well verify that this SU-DO-KU is properly done or not. That is why
we are saying solving the problem is difficult but verifying is easy. So such
kind of problem will say is a NP class problem. I hope you understood now. Now the NP
class problem as we already discussed clarification is very easy, verification
takes polynomial time. It means what, it is hard to solve, easy to verify, and it
takes exponential time. So I can say, let us say it is set we are saying that
whatever comes under this set is of NP class. okay, Now let us talk about P class
problem. We know that not only we can solve it in polynomial time but we can
verify it also in polynomial time. If a data is given to sort then not only I
can sort it, takes polynomial time but if sorted data is there I can verify
whether the data is properly sorted or not also in polynomial time.
Okay, so P class problem will be solved in polynomial time as well as verified
in polynomial time. So it is easy to solve, it is easy to verify and it takes
polynomial time. So obviously P class problem is inside the NP class problem.
NP class problem takes those problem which are difficult to solve, easy to verify. P
class problem takes those problem which are easy to solve and easy to verify.
Then I can say P is a subset of NP. Along with that those problem which comes
under P is called a tractable problem and those problem which comes under NP are called in practical problems. It is a million dollar question, till now nobody
has solved it. Is P equal to NP. Now we see before trying or before thinking
about P equal to NP or not. What are the implication ? If somebody proves that P is equal to NP then happen. If somebody can prove that
problem P is equal to NP information security or online security are really
really vulnerable to attack. And everything becomes much more efficient
such as transportation problems scheduling problem, understanding your
DNA… all these things becomes easy to understand. At the same time, your
security becomes very very vulnerable. Because all the security algorithms
comes under NP, difficult to find a solution but if a solution is there it
is easy to verify it. But if those security problems becomes P problems
means easy to solve any easy to verify then obviously the information
securities are vulnerable to attacks. Okay, on the other way, if somebody proves P is not equal to NP and then you can boldly say there are some problems that
cannot be solved. It is also a very big challenge to say there are problems
which cannot be solved. Now let us see what is a reduction. Let us say, a problem
A is given to me and I can convert it to problem B. And this reduction from
problem A to problem B supposed to take a polynomial. It means I can say, let A and
B are two polynomials then problem A reduces to problem B if and only if
there is a way to solve A by deterministic algorithm that solves
B in polynomial time. If I want to show that A can be solved in polynomial
time then I I don’t know yet, but I know that B can be solved for in polynomial
time, then what I do ? I reduce A to B and I’ll solve B and after solving B as B
can be solved in polynomial time I can say, A is also in polynomial time
problem. So if A is reducible to B then it is written as A is proportional to B.
Now let us see the properties of production. If A is reducible to B and B
is in P, is a polynomial time, I can solve. then I can say A is also can be solved
in polynomial time. The second property is if A is not in P then it implies B is
also not in P. We are going to use these properties in the next videos to come.
Now let us see what is NP-Hard problem. So a problem is NP-Hard if every problem
of NP can be polynomially reduced to it. Let us see diagrammatically, so these
are my NP problem and if I am having a set then all the problems of NP can
be reduced to this particular set and the reduction will take polynomial time
then I’ll say this set is NP-Hard. Now let us see what is NP-Complete
problem. The definition is, the problem is np-complete if it is in NP and it is
np-hard. It means, we are going to reduce it. We are using reduction formula. Let us
see here is the NP problem and here is the reduction problem. So NP is reduced
to NP hard, this part is NP-Hard, again to which part of this NP-Hard problem those
are in NP. So if we are reducing this NP problem to this particular part and
this particular part belongs to NP and this reduction will take polynomial time
this red part , we will say, is a NP-Complete Problem. It means what ? The class of NP-Complete problem is a intersection of NP and
NP-Hard classic of problem. So we know that the
intersection part is NP-Complete and this part is NP-Hard,
then NP-Complete problem are basically are the decision problems and the
NP-Hard problems are basically are the optimization problem. If a problem A is
an decision problem, it means it is an np-complete problem then we can convert this problem to optimization problem. That is a NP-Hard problem.
For example, a knapsack decision problem can be converted to knapsack
optimization problem. So I can say decision problems can be converted to a
optimization problem. All the NP-Complete problems are NP-Hard but all the NP-Hard
problems are not NP-Complete. It is evident from this particular diagram
because the intersection part only comes under NP-Complete. There is a large
portion which comes under NP-Hard. All the portion of NP-Hard is he doesn’t
comes under this intersection. So that’s why NP-Complete problems can be NP-Hard but all the NP-Hard problems cannot be NP-Complete. so what we learn ? When we are talking about computational complexity problem we can divide their problem into
either P class or NP class. Again NP class problem can be either
NP-Hard or NP-Complete. So in our next video we are going to discuss about different
theorem proving using this NP-Hard NP-Complete, P and NP set of problems.
So keep watching… keep learning … Thank you for watching this video till
the end. Please share this video with your friends. Thank You

Leave a Reply

Your email address will not be published. Required fields are marked *