揭示验证器效率与证书长度的权衡关系，构建新理论框架。
A Verifier Hierarchy
- 证明证书长度与验证时间存在数学下界关系。
- 提出基于证书复杂度的分层体系，适用于多个难题分析。
- 为P vs NP等核心问题提供新视角，适合理论计算机研究者。
我们研究证书长度与验证器运行时间之间的权衡。证明了验证语言的固有验证时间从 $f(n)$ 降低到 $g(n)$（$f(n) \ge g(n)$）时，证书长度至少为 $Ω(\log(f(n) / g(n)))$。该定理催生了一个基于证书复杂度的自然层次结构。我们展示了其在分析复杂度类分离假设（如 $ p$ 与 $ ext{exptime}$）以及研究字符串周期性、旋转检测等自然问题中的适用性。此外，通过关联子线性证书的存在性，为 $ ext{p}$ vs. $ p$ 问题提供了新见解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。