We defined a polynomial-time verifier so that it has certificates of length AT MOST p(|x|) for some fixed polynomial p.
Why does it not make a difference to require a certificate $c$ to have EXACLTY length p(|x|)?
1 Answer
$\begingroup$
$\endgroup$
Instead of a variable-length certificate $c$, you can always modify the certificate to have the form $\text{len}(c), c, 00\cdots 0$ where you append enough zeros to pad it out to the max length, thus yielding a fixed-length certificate.
