中央研究院 資訊科學研究所

The notion of 2nd order computability occurs naturally in many practical and theoretical settings. For examples, machine learning, programming languages, databases inquiry, complexity-theoretic problem reductions, and so on can be better modeled as 2nd-ordered computation. However, there is no generally accepted type-2 complexity theory to characterize the computational cost of such computation.  In this talk, I will introduce a theoretical framework for theorists to construct a complexity structure of 2nd-ordered computation.

The standard Oracle Turing Machine (OTM) will be used as our formalism for 2nd-ordered computation. The first step is to give a robust notion of 2nd-ordered complexity classes. This is not as intuitive as the classical complexity classes. We define an induced topology determined by 2nd-ordered continuous functionals. Based on the compact sets in such topology, we define a 2nd-ordered asymptotic notation, in such a way, we can define a 2nd-ordered big-O notation, which seems to be a useful tool for 2nd-ordered algorithm analysis.

However, our 2nd-ordered big-O notation needs to be justified by some theoretical theorems. I will also discussed those required theorems under our framework. In particular, we need a type-2 analog of the classical Union Theorem, which turn out to be a very strong theorem in 2nd-order computation.