The Complexity of Computing with Infinite Data

点击翻译按钮获取中文摘要

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.