The Complexity of Computing with Infinite Data

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