A Verifier Hierarchy
This work addresses foundational questions in theoretical computer science, particularly for researchers studying complexity classes and verification, but it is incremental as it builds on existing concepts in complexity theory.
The paper tackles the trade-off between certificate length and verifier runtime in computational complexity, proving a Verifier Trade-off Theorem that establishes a lower bound on certificate length when reducing verification time, and applies this to analyze separations between complexity classes like NP and EXPTIME, as well as problems like string periodicity.
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 \(Ω(\log(f(n) / 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., \(\np\) and \(\exptime\)) and to studying natural problems such as string periodicity and rotation detection. Additionally, we provide perspectives on the \(\p\) vs. \(\np\) problem by relating it to the existence of sub-linear certificates.