A Verifier Hierarchy

We investigate the trade-off between certificate length and verifier runtime. We prove a Verifier Trade-off Theorem showing that reducing the inherent verification time of a language from $f(n)$ to $g(n)$, where $f(n)\ge g(n)$, requires certificates of length at least $\mathrm{\Omega }(\log (f(n)\mathrm{/}g(n)))$. This theorem induces a natural hierarchy based on certificate complexity. We demonstrate its applicability to analyzing conjectured separations between complexity classes (e.g., $\text{np}$ and $\text{exptime}$) and to studying natural problems such as string periodicity and rotation detection. Additionally, we provide perspectives on the $\text{p}$ vs. $\text{np}$ problem by relating it to the existence of sub-linear certificates.