从功能不确定性传感器到确定性双磁带自动机（CS CC）---蔡秋纯

P = NP的问题围绕着有效生产与图灵机验证之间的差异。在本文中，我们研究了有限换能器和自动机的类似问题。每个不确定的有限换能器都定义一个二进制关系，将输入字与输出字相关联，该输入字由换能器计算并接受。功能转换器是关系是函数的转换器，我们对功能不确定的传感器进行了表征，它们的关系可以通过确定性的两带式自动机进行验证，展示了如何构造这种自动机（如果存在），并证明了该标准的不确定性。

原文标题：From Functional Nondeterministic Transducers to Deterministic Two-Tape Automata

原文：The question whether P = NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem for finite transducers and automata. Every nondeterministic finite transducer defines a binary relation associating input words with output words that are computed and accepted by the transducer. Functional transducers are those for which the relation is a function. We characterize functional nondeterministic transducers whose relations can be verified by a deterministic two-tape automaton, show how to construct such an automaton if one exists, and prove the undecidability of the criterion.

原文作者：Elisabet Burjons, Fabian Frei, Martin Raszyk

原文地址：https://arxiv.org/abs/2005.13710