Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918476633866240 |
|---|---|
| author | Chen, Zeyu Wu, Junde |
| author_facet | Chen, Zeyu Wu, Junde |
| contents | Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur--Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in $\mathbf{ATIME}(2^{O(n)})$, and perfect-completeness strong verification for every language in $\mathbf{PSPACE}$. These results establish that the remarkable verification power of affine finite-state automata is structural. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07857 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems Chen, Zeyu Wu, Junde Formal Languages and Automata Theory Computational Complexity Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur--Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in $\mathbf{ATIME}(2^{O(n)})$, and perfect-completeness strong verification for every language in $\mathbf{PSPACE}$. These results establish that the remarkable verification power of affine finite-state automata is structural. |
| title | Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems |
| topic | Formal Languages and Automata Theory Computational Complexity |
| url | https://arxiv.org/abs/2509.07857 |