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.
翻译:Hartmanis和Simon(Hartmanis和Simon,1974年)以及Floyd和Knuth(Floyd和Knuth,1990年)先前的工作调查了如果一个装置使用原始步骤比图灵磁带的单一更新更自然,会发生什么情况,一项调查结论是,在数字设置中,加、减、比较和对比波林操作中,数字保存多球时间,同时结合结合或乘数,可以在许多步骤中解决PSPACE的所有问题。因此,我们提议使用自动功能进行更新和比较,作为原始操作,并经常使用许多登记册;由此产生的模型涵盖哈特曼斯和西蒙以及弗洛伊德和Knuth的所有原始作业,但模型仍停留在多球时间。目前的工作特别调查了各种自然问题的决定性复杂性,并概述了这一模型的非决定性复杂性。