
And the answer is pis indeed contained within np and the reason is if the problem that we had

can be decided by some polynomial time algorithm s that takes the input, runs in polynomial time,

and either says yes or no correctly for that input, then we can design

remember that the main thing in the definition of np is that it has a verification algorithm,

so we can define a verification algorithm like thisdefine a to take the input and any certificate

that simply returns s of xthis runs in polynomial time and it accepts inputs and certificates correctly.

So for any input x, there's some certificate that makes it say yesthat is to say any certificate

because if the answer is yes, it's always going to return yes.

And if the answer is no, there's no certificate you can give it

that would get it to say anything other than no.

That's again because it's a growing certificate and actually just giving the answer.

So it's satisfies the two things that we need for the problem to be an np.

So anything np is also an np.