Quantum and Reversible Verification of Proofs Using Constant Memory Space
Quantum and Reversible Verification of Proofs Using Constant Memory Space
复制标题
DOI：
10.1007/978-3-319-13749-0_13
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Marcos Villagra;T. Yamakami
中科院分区：
文献类型：
--
作者：
Marcos Villagra;T. Yamakami
在NP语言中，确定性验证者与强大证明者在多项式时间内对证明或证书的非交互验证被用来描述语言。我们通过量子验证器和可逆验证器开始研究类似的非交互证明验证过程的计算复杂性，这些验证器只被允许使用恒定数量的内存存储。通过将弱验证器建模为量子和可逆有限自动机，我们研究了这种非交互证明系统的基本性质，并证明了允许验证器必须实时扫描输入的证明系统的语言正是正则语言。相反，当我们允许验证者向各个方向移动磁头时，相应的证明系统被授权识别非随机、非上下文无关和NP-完全语言。
Non-interactive verification of proofs or certificates by deterministic verifiers in polynomial time with mighty provers is used to characterize languages in NP. We initiate the study of the computational complexity of similar non-interactive proof-verification procedures by quantum and reversible verifiers who are permitted to use only a constant amount of memory storage. By modeling those weak verifiers as quantum and reversible finite automata, we investigate fundamental properties of such non-interactive proof systems and demonstrate that languages admitting proof systems in which verifiers must scan the input in real time are exactly regular languages. On the contrary, when we allow verifiers to move their tape heads in all directions, the corresponding proof systems are empowered to recognize non-stochastic, non-context-free, and NP-complete languages.