pith. sign in

arxiv: 2006.12330 · v2 · submitted 2020-06-22 · 💻 cs.CC · cs.FL

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error

M. Utkan Gezer , A. C. Cem Say This is my paper

Pith reviewed 2026-05-24 14:31 UTC · model grok-4.3

classification 💻 cs.CC cs.FL
keywords constant spaceconstant randomnessprobabilistic verifiersNLmulti-head automataerror reductionlinear time
0
0 comments X

The pith

Languages recognized by linear-time multi-head nondeterministic automata have constant-coin constant-space verifiers with arbitrarily small error.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that any language recognizable by a linear-time multi-head nondeterministic finite automaton admits a verifier using only a fixed number of coin tosses and constant space that achieves an error probability below any chosen positive value. Earlier work had shown that constant-coin constant-space verifiers can recognize exactly the class NL when the allowed error is any number strictly less than one half. The new result identifies a natural subclass of NL where the error can be driven down without increasing the number of coins or the space used. A reader would care because it highlights how the linear-time multi-head property enables reliable probabilistic verification with severely limited resources.

Core claim

For any ε > 0, one can construct a constant-coin, constant-space verifier operating within error ε for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa(k)). The construction does not extend easily to the full class NL, and the power of these automata relates to simultaneous time-space complexity classes of Turing machines.

What carries the argument

The error-reduction construction that leverages the linear-time recognition by multi-head nondeterministic automata to amplify the success probability without additional coins or space.

If this is right

  • Every linear-time 2nfa(k) language has a constant-coin constant-space verifier with error less than any ε > 0.
  • The class of linear-time 2nfa(k) languages is contained in the languages verifiable with constant randomness and space at arbitrarily low error.
  • It is difficult to generalize the low-error verification method to all of NL.
  • The power of linear-time 2nfa(k) can be related to simultaneous time-space complexity classes defined in terms of Turing machines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear-time restriction may be key to allowing error amplification with bounded randomness in verification.
  • Similar techniques could apply to other automaton models that have linear-time recognition properties.
  • This result leaves open whether the full NL requires more than constant coins for low error.
  • The connection to time-space classes might help identify other languages with this property.

Load-bearing premise

The error reduction works only when the language can be recognized by a linear-time multi-head nondeterministic finite automaton.

What would settle it

A specific language recognizable by some linear-time 2nfa(k) for which every constant-coin constant-space verifier has error probability bounded away from zero by some positive constant would falsify the claim.

Figures

Figures reproduced from arXiv: 2006.12330 by A. C. Cem Say, M. Utkan Gezer.

Figure 1
Figure 1. Figure 1: State diagram of 2nfa(2) MEQ . q0 q1 q2 qacc qrej ⊲ → +1 0 → 0 0 → +1 ⊳ → 0 0 → +1 1 → 0 [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: State diagram of 2nfa MEQ1 . loops indefinitely on q1 given any input string that begins with a 0. Thus, MEQ1 is not always halting, and by Definition 1, the first head of MEQ is risky. Indeed, µ1(EQ) simulating MEQ and running on an input string that begins with 0 would loop forever at state q1 if µ1(EQ) were to track the first head, and the certificate were to report infinite sequences of 0’s as both hea… view at source ↗
Figure 3
Figure 3. Figure 3: State diagram of 2nfa MEQ2 . Lemma 6. Being safe or risky is a decidable property of a 2nfa(k)’s heads. Proof. To decide whether the i th head of a 2nfa(k) M is safe, an algorithm can construct the 2nfa Mi described in Definition 1 and test whether Mi ∈ HALTING2nfa by the algorithm in Lemma 5. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Inclusion diagram of the language classes covered [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
read the original abstract

We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakary{\i}lmaz showed that the class of languages that could be verified by these machines within an error bound strictly less than $1/2$ is precisely NL, but their construction yields verifiers with error bounds that are very close to $1/2$ for most languages in that class when the definition of "error" is strengthened to include looping forever without giving a response. We characterize a subset of NL for which verification with arbitrarily low error is possible by these extremely weak machines. It turns out that, for any $\varepsilon>0$, one can construct a constant-coin, constant-space verifier operating within error $\varepsilon$ for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa($k$)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa($k$)'s to simultaneous time-space complexity classes defined in terms of Turing machines.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that for any ε > 0, every language recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa(k)) admits a constant-coin, constant-space probabilistic verifier whose error probability (including non-halting) is at most ε. The construction is shown not to extend to all of NL, and the power of linear-time 2nfa(k) is related to simultaneous time-space complexity classes of Turing machines.

Significance. If the stated construction holds, the result isolates a natural fragment of NL for which constant-randomness, constant-space verification with arbitrarily small error is possible, sharpening the boundary between the Say-Yakaryılmaz NL characterization (error close to 1/2) and stronger error reduction. The explicit time-space relation supplies a concrete link between automaton and Turing-machine models that may aid further work on space-bounded verification.

minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from an explicit statement of the precise model of certificate access (one-way vs. two-way, read-only vs. read-write) used by the verifier.
  2. A short table or diagram comparing the error bounds and resource usage of the new construction against the Say-Yakaryılmaz verifier would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept the manuscript and for the accurate summary of our results on constant-coin constant-space verification for linear-time 2nfa(k) languages.

Circularity Check

0 steps flagged

Minor self-citation not load-bearing; core construction independent

full rationale

The paper establishes an existence result via explicit construction: for any ε>0, languages recognized by linear-time 2nfa(k) admit constant-coin constant-space verifiers with error <ε. The sole self-citation (to Say and Yakaryılmaz on the NL characterization with error <1/2) supplies background context for the broader class but is not invoked to derive or justify the new construction for the linear-time subset; the paper instead supplies its own argument for why the method does not extend to full NL and relates the subclass to time-space bounds. No equations, fitted parameters, ansatzes, or uniqueness theorems reduce the central claim to prior inputs or self-references. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of NL, 2nfa(k), and probabilistic finite automata; no new free parameters, axioms beyond standard mathematics, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and closure properties of nondeterministic finite automata and probabilistic verifiers from complexity theory
    Invoked throughout the abstract when relating 2nfa(k) to NL and when stating verifier constructions.

pith-pipeline@v0.9.0 · 5760 in / 1175 out tokens · 24575 ms · 2026-05-24T14:31:17.706100+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    M. U. Gezer, Windable heads and recognizing NL with const ant randomness, in: A. Leporati, C. Martín-Vide, D. Shapira, C. Zandron 19 (Eds.), Language and Automata Theory and Applications, Spr inger International Publishing, Cham, 2020, pp. 184–195

    work page 2020

  2. [2]

    Condon, R

    A. Condon, R. Ladner, Interactive proof systems with pol ynomially bounded strategies, Journal of Computer and System Science s 50 (3) (1995) 506–518

    work page 1995

  3. [3]

    Condon, R

    A. Condon, R. J. Lipton, On the complexity of space bounde d interactive proofs, in: 30th Annual Symposium on Foundations of Compute r Science, 1989, pp. 462–467

    work page 1989

  4. [4]

    Dwork, L

    C. Dwork, L. Stockmeyer, Finite state verifiers I: The pow er of interaction, J. ACM 39 (4) (1992) 800–828

    work page 1992

  5. [5]

    Nishimura, T

    H. Nishimura, T. Yamakami, An application of quantum fini te automata to interactive proof systems, Journal of Computer and Syste m Sciences 75 (4) (2009) 255–269

    work page 2009

  6. [6]

    Nishimura, T

    H. Nishimura, T. Yamakami, Interactive proofs with quan tum finite automata, Theoretical Computer Science 568 (2015) 1–18

    work page 2015

  7. [7]

    Yakaryılmaz, Public qubits versus private coins, in: Workshop on Quantum and Classical Complexity, University of Latvia Pre ss, Riga, 2013, pp

    A. Yakaryılmaz, Public qubits versus private coins, in: Workshop on Quantum and Classical Complexity, University of Latvia Pre ss, Riga, 2013, pp. 45–60, ECCC:TR12-130

    work page 2013

  8. [8]

    Zheng, D

    S. Zheng, D. Qiu, J. Gruska, Power of the interactive proo f systems with verifiers modeled by semi-quantum two-way finite automata, I nformation and Computation 241 (2015) 197–214

    work page 2015

  9. [9]

    Feige, A

    U. Feige, A. Shamir, Multi-oracle interactive protocol s with constant space verifiers, Journal of Computer and System Sciences 44 ( 2) (1992) 259–271

    work page 1992

  10. [10]

    H. G. Demirci, A. C. C. Say, A. Yakaryılmaz, The complexi ty of debate checking, Theory of Computing Systems 57 (1) (2015) 36–80

    work page 2015

  11. [11]

    Yakaryılmaz, A

    A. Yakaryılmaz, A. C. C. Say, H. G. Demirci, Debates with small transparent quantum verifiers, International Journal of Fo undations of Computer Science 27 (02) (2016) 283–300

    work page 2016

  12. [12]

    A. C. C. Say, A. Yakaryılmaz, Finite state verifiers with constant randomness, Logical Methods in Computer Science 10 (3) (Aug . 2014)

    work page 2014

  13. [13]

    Sipser, Introduction to the Theory of Computation, C engage Learning, 2012

    M. Sipser, Introduction to the Theory of Computation, C engage Learning, 2012

    work page 2012

  14. [14]

    Holzer, M

    M. Holzer, M. Kutrib, A. Malcher, Complexity of multi-h ead finite automata: Origins and directions, Theoretical Computer Sc ience 412 (1-2) (2011) 83–96. 20

    work page 2011

  15. [15]

    Hartmanis, On non-determinancy in simple computing devices, Acta Informatica 1 (4) (1972) 336–344

    J. Hartmanis, On non-determinancy in simple computing devices, Acta Informatica 1 (4) (1972) 336–344

    work page 1972

  16. [16]

    Monien, Two-way multihead automata over a one-lette r alphabet, RAIRO

    B. Monien, Two-way multihead automata over a one-lette r alphabet, RAIRO. Inform. théor. 14 (1) (1980) 67–82

    work page 1980

  17. [17]

    R. E. Ladner, R. J. Lipton, L. J. Stockmeyer, Alternatin g pushdown automata, in: Proceedings of 19th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 19 78, pp. 92–106

    work page

  18. [18]

    Geffert, A

    V. Geffert, A. Okhotin, Transforming two-way alternati ng finite automata to one-way nondeterministic automata, in: International S ymposium on Mathematical Foundations of Computer Science, Springer, 2 014, pp. 291–302

    work page

  19. [19]

    Holzer, M

    M. Holzer, M. Kutrib, Descriptional and computational complexity of finite automata—A survey, Information and Computation 209 ( 3) (2011) 456–470

    work page 2011

  20. [20]

    Condon, The complexity of the max word problem and the power of one-way interactive proof systems, computational complex ity 3 (3) (1993) 292–305

    A. Condon, The complexity of the max word problem and the power of one-way interactive proof systems, computational complex ity 3 (3) (1993) 292–305

    work page 1993

  21. [21]

    Cobham, Time and memory capacity bounds for machines which recognize squares or palindromes, IBM Res

    A. Cobham, Time and memory capacity bounds for machines which recognize squares or palindromes, IBM Res. Rep. RC-1621 (19 66)

    work page

  22. [22]

    van Melkebeek, Time-space lower bounds for NP-compl ete problems, in: G

    D. van Melkebeek, Time-space lower bounds for NP-compl ete problems, in: G. Plun, G. Rozenberg, A. Salomaa (Eds.), Current Trends in Theoretical Computer Science, World Scientific, 2004, pp. 2 65–291

    work page 2004

  23. [23]

    Dúriś, Z

    P. Dúriś, Z. Galil, A time-space tradeoff for language re cognition, Mathematical systems theory 17 (1) (1984) 3–12. 21

    work page 1984