论文标题
部分可观测时空混沌系统的无模型预测
Turing Machines with Two-level Memory: A Deep Look into the Input/Output Complexity
论文作者
论文摘要
许多前研究人员对主要内存和外部内存之间数据交换的复杂性（这是数据交换的复杂性）进行了精心研究。但是，现有作品未能在计算模型的角度考虑输入/输出复杂性。在本文中，我们通过提出三种图灵机的变体来补救此问题，该机器包括外部内存以及在主内存和外部内存之间交换数据的机制。基于这些新模型，深入研究了输入/输出复杂性。我们讨论了输入/输出复杂性与其他复杂性等其他复杂性度量之间的关系，例如时间复杂性和参数化的复杂性，这是前研究人员不考虑的。我们还定义了外部访问痕量复杂性，这反映了磁盘的物理行为，并提供了IO效率算法的理论证据。
The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computation model point of view. In this paper we remedy this by proposing three variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discussed the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms.
