What is a certificate in plain english?
For example, the compositeness problem, &quot;given an integer $X$, is it composite?&quot; might have a certificate $n_1, n_2$ where $X=n_1n_2$. This certificate would be checkable in time polynomial in the length of the certificate.