Complexity Theory for 2nd order Computation
- LecturerProf. Chung-Chih Li (Illinois State University)
Host: Chi-Jen Lu - Time2013-04-23 (Tue.) 10:30 ~ 12:00
- LocationAuditorium 106 at new IIS Building
Abstract
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.