Real-time, constant-space, constant-randomness verifiers
From MaRDI portal
Publication:2164756
DOI10.1007/978-3-031-07469-1_17OpenAlexW4281687983MaRDI QIDQ2164756
Özdeniz Dolu, Nevzat Ersoy, A. C. Cem Say, Mehmet Utkan Gezer
Publication date: 16 August 2022
Full work available at URL: https://arxiv.org/abs/2206.00968
Related Items (2)
Cites Work
- The complexity of debate checking
- Complexity of multi-head finite automata: origins and directions
- On 3-head versus 2-head finite automata
- Interactive proof systems with polynomially bounded strategies
- Set Automata
- Finite state verifiers with constant randomness
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- k + 1 Heads Are Better than k
- Computational Complexity
- On Multi-Head Finite Automata
This page was built for publication: Real-time, constant-space, constant-randomness verifiers