A Verifier Hierarchy
Maurits Kaptein · 2025
Read A Verifier Hierarchy by Maurits Kaptein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23504.txt.
Introduction
Maurits Kaptein wrote this 2025 paper on a trade-off at the heart of computation: proof length against checking time. A verifier is a program that checks a certificate, a claimed proof that some input has a property. Shorter checks may demand longer proofs, and Kaptein makes that exchange precise.
His trade-off theorem says that cutting the natural checking time from one level to a lower one forces certificates at least a set length, set by the gap between the two times. That rule sorts problems into a hierarchy by certificate size. He applies it to famous open separations between complexity classes, and to concrete problems like detecting periods and rotations in strings. The view also reframes the P versus NP question: it becomes a question of whether ultra-short certificates can exist.
Catalog record
| CREATOR | Maurits Kaptein |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23504
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Verifier Hierarchy Maurits Kaptein Abstract 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 ) f(n) to g ( n ) g(n) , where f ( n ) ≥ g ( n ) f(n)\geq g(n) , requires certificates of length at least Ω ( log ( f ( n ) / g ( n ) ) ) \Omega(\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. 1 Introduction Hierarchy theorems have long been indispensable tools for separating complexity classes and understanding computational hardness. The deterministic time hierarchy theorem [ 1 ] established the strict separation of polynomial time P from exponential time EXPTIME , while space hierarchy theorems [ 2 ] delineate distinct space complexity classes. Similarly, nondeterministic time hierarchy theorems [ 3 , 4 , 5 ] reveal subtler separations for nondeterministic Turing machines (NTMs). These results underscore the foundational role of hierarchies in complexity theory. In this work, we introduce a novel hierarchy theorem that bridges deterministic and nondeterministic computation through certificate complexity. Building on the equivalence of NTMs and deterministic verifiers for NP [ 6 , as reprinted in] , we establish a hierarchy of verifiers where certificate length governs computational speed-ups. Formally, suppose that for a language L and two certificate-length functions b_{1}(n)<b_{2}(n) we have: • Every verifier for L using b_{1}(n) -bit certificates requires at least \Omega(f(n)) time (the inherent verification time). • There exists a verifier for L using b_{2}(n) -bit certificates that runs in O(g(n)) time, with f(n)\geq g(n) . We prove in Theorem 4.1 that b_{2}(n)-b_{1}(n)=\Omega\left(\log\frac{f(n)}{g(n)}\right). This captures the trade-off: reducing a language’s inherent verification time from f(n) to g(n) forces an additive certificate-length increase of \Omega\left(\log(f/g)\right) , yielding a strict hierarchy of verifier complexity. Anchoring our analysis in the verifier-based view of NP , we illustrate three applications of the Verifier Trade-off Hierarchy: • Hierarchy Alignments. We demonstrate how our theorem aligns with classic separations like \textsf{P}\subsetneq\textsf{EXPTIME} . For example, any language in EXPTIME with a polynomial-time verifier requires super-polynomial certificates. • Case Studies on Natural Problems. We analyze two canonical string-manipulation languages, PERIODIC and STRING-ROTATION , deriving bounds on the certificate length vs. verification time trade-off. • Certificate-Size Lens on P vs. NP . We recast the P vs. NP question in terms of certificate length: – Linear certificates for NP -complete languages align with the classical definition of NP . – Sub-linear certificates would collapse P and NP , suggesting \textsf{P}=\textsf{NP} . We concretize the latter by analyzing 3-SAT , highlighting certificate size as a critical resource. In the remainder of this paper, we first briefly review related work (Section 2 ) and then introduce notation and definitions (Section 3 ). Section 4 presents our main Verifier Trade-off Hierarchy Theorem and corollaries. In Section 5 we discuss implications, analyze natural problems, and explore complexity class separations. Section 6 provides pointers for future work. 2 Related Work Classical hierarchy theorems delineate separations within computational models. For example, the deterministic time hierarchy theorem [ 1 ] establishes that sufficiently increasing time strictly enlarges computable classes (e.g., \textsf{P}\subsetneq\textsf{EXPTIME} ). Analogous hierarchies for NTMs require super-polynomial time gaps, reflecting the subtler structure of nondeterminism [ 7 ] . These results, while foundational, focus on separations within paradigms. Our work bridges across them: we quantify how certificate size mediates the computational advantage of verification over solving, complementing hierarchy theorems with a dimension orthogonal to time/space. The definition of NP via polynomial-time verifiers [ 6 ] inspired our certificate-centric approach. Subsequent verification paradigms—interactive proofs [ 8 ] , probabilistically checkable proofs (PCPs) [ 9 ] , and automatizability of proof systems [ 10 ] —shifted focus to distributed, randomized, or heuristic verification. For instance, [ 10 ] showed that efficient automatizability of resolution proofs would imply unexpected circuit lower bounds, highlighting the interplay between proof length and computational hardness. In contrast, our framework isolates certificate size as the critical resource, rather than interaction or randomness, mirroring classical hierarchy intuitions in a new dimension. Non-uniform computation augments deterministic machines with advice strings fixed per input length [ 11 , 12 ] , while certificate complexity [ 6 ] measures minimal proof lengths for Boolean functions [ 13 , see, e.g.,] . Our work diverges by treating certificates as efficiency parameters governing possible language verification speed-ups, rather than static advice or worst-case bounds. This aligns with circuit-based approaches like [ 14 ] ’s proof of Toda’s theorem [ 14 ] , which leverages circuit complexity to ascend the polynomial hierarchy, but with a focus on dynamic proofs rather than fixed circuit families. Modern complexity theory emphasizes fine-grained lower bounds under conjectures like the Exponential Time Hypothesis ( \mathsf{ETH} ) [ 15 , 16 ] and tools from fine-grained complexity [ 17 , e.g.,] . These results often assume hardness to derive precise time constraints (e.g., for 3-SAT ). Our hierarchy theorem complements this by deriving certificate size lower bounds from structural problem properties. For example, connections between combinatorial games and proofs, as in [ 18 ] ’s work on mean-payoff games and propositional proofs [ 18 ] , reveal how problem structure constrains proof complexity—a theme our work extends to certificate-mediated verification. 3 Preliminaries In this section, we establish the formal framework necessary for analyzing the relationship between certificate size and computational speed-up. We begin by defining the computational models under consideration and subsequently we introduce the remainder of the notation and definitions that will be used throughout the paper. 3.1 Defining Solvers and Verifiers We consider languages over the finite alphabet \Sigma=\{0,1\} . For a string x\in\Sigma^{*} , let |x| denote its length. We use \Sigma^{*} to denote the set of all finite-length strings over \Sigma (including the empty string \varepsilon ), and \Sigma^{+} to denote the set of nonempty strings over \Sigma , i.e., \Sigma^{+}=\Sigma^{*}\setminus\{\varepsilon\} . A language L is a subset of \Sigma^{*} . Definition 3.1 (Certificate-Based Deterministic Verifier) . A certificate-based verifier V for a language L is a deterministic Turing machine that takes as input a pair (x,w) , where x\in\Sigma^{*} is the instance and w\in\{0,1\}^{*} is a certificate. For all x\in L , there exists a certificate w such that V(x,w)=1 (acceptance). For all x\not\in L and all certificates w , V(x,w)=0 (rejection). Definition 3.2 (Certificate Length) . For a verifier V and input length n , the certificate length b(n) is the maximum length of any certificate w required for inputs x\in L with |x|=n . Definition 3.3 (Deterministic Solver) . A deterministic solver S for L is a deterministic Turing machine that, on input x\in\Sigma^{*} , outputs S(x)=1 if x\in L and S(x)=0 otherwise. Equivalently, S is a verifier with certificate length b(n)=0 . Solvers are closed under complement: if S decides L in time T_{S}(n) , then its