The Complexity of Computing with Infinite Data

传统的计算复杂性理论处理有限输入的计算，如自然数或有限图。然而，在许多情况下，考虑对无限输入数据的计算是很自然的。例如，许多编程语言支持无限数据，如流或高阶函数，并且这些语言的许多语义模型本质上是连续的。在可计算实数分析中，采用基于实数可计算性的模型对数值计算进行抽象。在普通的复杂性理论和密码学中，关于预言的计算被用来理解类和假设之间的关系。作为最后一个例子，构造形式系统的证明理论的许多方法依赖于高阶可计算函数。从图灵的可计算实数模型开始，关于无限数据的可计算性已经有了相当多的研究，但总的来说，这些模型和复杂性理论之间的交集仍然相对未被探索。我的研究目标是完善我们对无限数据计算复杂性的理解。虽然这项工作是基础兴趣，但它有可能影响各种应用，包括利用高阶特征或执行数值计算的程序效率的推理技术，数学公理复杂性的基础结果，以及更好地理解NP搜索问题类别之间的关系以及加密证明中预言机的使用。我的方法的指导原则是保留计算的有限性：计算的长度是有限的，存储是有限的，任何输入或输出操作只涉及有限数量的数据。因此，输入数据的表示成为一个中心问题。我将使用很容易理解的模型，比如普通的图灵机接受有限的输入（类型一）或配备一个oracle（类型二），并制定输入表示来模拟无限的输入。这种方法在计算研究中很常见，并且可能导致捕获复杂性的模型。例如，实值函数的计算可以在第一类设置中建模，通过考虑由有理近似表示的输入和输出；在这种情况下，也可以对复杂性进行建模。将可计算函数作为输入的可计算运算符也可以在类型1设置中通过使用哥德尔数表示输入来建模，但在这种情况下，没有简单的方法来建模复杂性。对于许多应用程序，有必要超越类型1框架。这包括分析中运算符的复杂性、搜索复杂性和构造逻辑的解释。我提出的研究是建立在我之前关于类型级别2和更高级别的复杂性的工作的基础上，同时探索基于针对特定于应用程序的输入域的表示的新方法。

Traditional computational complexity theory deals with computation on finite inputs, such as natural numbers or finite graphs. However, in many settings it is natural to consider computation over infinitary input data. For example, many programming languages support infinitary data such as streams or higher-order functions, and many semantic models for these languages are inherently continuous. In computable real analysis, models based on computability over real numbers are used to abstract numerical computation.  In ordinary complexity theory and cryptography, computation with respect to oracles is used to understand the relationship between classes and assumptions. As a final example, many approaches to the proof theory of constructive formal systems rely on higher-order computable functions. There has been considerable work on computability over infinite data, dating back to Turing's model for computable real numbers, but in general the intersection between such models and complexity theory remains relatively unexplored. The goal of my research is to refine our understanding of the complexity of computing with infinite data. While this work is of fundamental interest, it has the potential to impact a variety of applications, including techniques for reasoning about the efficiency of programs that utilize higher-order features or perform numerical computation, foundational results on the complexity of mathematical axioms, and a better understanding of relationships between classes of NP search problems and the use of oracles in cryptographic proofs. A guiding principle in my approach is to retain the finitary nature of computation: computations have finite length, storage is finite, and any input or output operation involves only a finite amount of data. As a result, the representation of input data becomes a matter of central concern. I will use well-understood models, such as ordinary Turing machines taking finite inputs (type-one) or equipped with an oracle (type-two), and formulate input representations to model infinite inputs. This approach is common in the study of computation, and may lead to models which capture complexity. For example, computation of real-valued functions may be modeled in the type-one setting, by considering inputs and outputs represented by rational approximations; in this setting it is also possible to model complexity. Computable operators that take computable functions as input may also be modeled in the type-one setting by using Goedel numbers to represent inputs, but in this case there is no simple way to model complexity. For many applications it is necessary to go beyond the type-one framework. This includes the complexity of operators in analysis, search complexity, and interpretations of constructive logics. My proposed research builds on my previous work on complexity for type-level two and higher, while exploring new approaches based on representations tailored to application-specific input domains.