Scholarlink

<p>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 can benefit from only 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Classical and quantum Merlin–Arthur automata

  • 期刊论文

  • 发表日期：

    2025年12月5日

查看全文
  • Abuzer Yakaryılmaz

摘要

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 can benefit from only 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.