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