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\in L$, then there is a "proof"(or certificate) $t\in\{0,1\}^{p(|x|)}$ such that $M$ accepts the string $\langle x,t \rangle$
- If $x\notin L$, then for any string $t\in\{0,1\}^{p(|x|)}$, $M$ rejects $\langle x,t \rangle$
Firstly, are we saying that $M$ here is a universal turing machine, i.e. $M(\langle x,t\rangle)=M_x(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.