论文标题
具有自动功能和关系的计算模型作为原始操作
A Computation Model with Automatic Functions and Relations as Primitive Operations
论文作者
论文摘要
Hartmanis和Simon（Hartmanis and Simon，1974）以及Floyd和Knuth（Floyd and Knuth，1990）的先前工作调查了如果设备使用比图灵胶带的单个更新更自然的原始步骤会发生什么。一个发现是，在数值环境中，加法，减法，比较和位于位的布尔数字操作保留了多项式时间，同时结合了串联或乘法，可以在多个步骤中解决所有PSPACE问题。因此，我们建议将更新和比较与自动功能作为原始操作，并不断使用许多寄存器；所得模型涵盖了Hartmanis和Simon以及Floyd和Knuth的所有原始操作，但是该模型仍在多项式时间内。本工作特别研究了各种自然问题的确定性复杂性，还概述了该模型的非确定复杂性。
Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural than single updates of a Turing tape. One finding was that in the numerical setting, addition, subtraction, comparisons and bit-wise Boolean operations of numbers preserve polynomial time while incorporating concatenation or multiplication allows to solve all PSPACE problems in polynomially many steps. Therefore we propose to use updates and comparisons with automatic functions as primitive operations and use constantly many registers; the resulting model covers all primitive operations of Hartmanis and Simon as well as Floyd and Knuth, but the model remains in polynomial time. The present work investigates in particular the deterministic complexity of various natural problems and also gives an overview on the nondeterministic complexity of this model.
