In my lecture notes, the definition of the class NP is given as: A language L is

Question

In my lecture notes, the definition of the class NP is given as:

A language L is in the class NP, if there exists a turing machine M and polynomials T and p such that:

For every input x, M terminates after at most T(|x|) steps
If x?L, then there is a "proof"(or certificate) t?{0,1}p(|x|) such that M accepts the string ?x,t?
If x?L, then for any string t?{0,1}p(|x|), M rejects ?x,t?

Firstly, are we saying that M here is a universal turing machine, i.e. M(?x,t?)=Mx(t), also is it necessary to use the same t for all x.
Also M is checking whether or not x lies in the L, so shouldn't we run just input x on M, why is the t necessary. Is there any particular reason why t is called a certificate? Any help with understanding this definition would be greatly appreciated.

Explanation / Answer

We are not "saying that M here is a universal" Turing machine. It is not "necessary to use the same t for all x." What would running "input x on M" mean when M would use its other input?
t certifies x's membership in the NP language that corresponds to M and T
if and only if M accepts the string ?x,t? after at most T(|x|) steps

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.