论文标题
古典和量子Merlin-Arthur Automata
Classical and quantum Merlin-Arthur automata
论文作者
论文摘要
我们介绍Merlin-Arthur（MA）自动机，其中Merlin在计算开始时提供证书，并且在阅读输入之前，Arthur扫描了该证书。我们定义了Merlin-Arthur确定性，概率和量子有限状态自动机（分别，MA-DFAS，MA-PFAS和MA-QFAS），以及Seletselets MA-PFAS和MA-QFAS（分别，MA-POSTPFA和MA-POSTQFA）。我们使用不同的证书长度提出了几个结果。 我们表明，MA-DFA使用恒定长度证书，并且相当于多输入DFA。因此，他们认识到所有和唯一的普通语言，但是它们可以分别对二元和一级语言有效和多项式状态有效。有了sublinear长度证书，MA-PFA可以识别几种具有剪切点1/2的非策略符号的一条语言。使用线性长度证书，MA-POSTPFA可以识别具有有界错误的这些非策略的单语言。有了任意长的证书，有限的ma-postPFA可以验证每种一般性决定性的语言。有了符号长度证书，有限的eRror ma-postqfas可以验证几种非策略的单语言。使用线性长度证书，他们可以验证每种单语言和一些NP完整的二进制语言。使用指数长度证书，他们可以验证每种二进制语言。
We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate at the beginning of computation and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, and MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We present several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages, but they can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs can recognize these nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs can verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs can verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language.
