#### Title

Type-2 complexity theory

#### Date of Award

2001

#### Degree Type

Dissertation

#### Degree Name

Doctor of Philosophy (PhD)

#### Department

Electrical Engineering and Computer Science

#### Advisor(s)

Carlos Hartmann

#### Keywords

Complexity theory, Computability, Topology, Continuous functionals

#### Subject Categories

Computer Sciences | Mathematics | Physical Sciences and Mathematics

#### Abstract

The notion of type-2 computability occurs naturally in many practical and theoretical settings in computer science. For examples, machine learning, programing languages, databases enquiry, complexity-theoretic problem reductions, and so on, are immediate applications of type-2 computation. However, there is no satisfactory type-2 complexity theory to characterize the computational cost of these widely ranged applications. Thus, the purpose of this thesis is to give a theoretical framework for analyzing the complexity of type-2 computation.

We use the Oracle Turing Machine (OTM) as our standard formalism for type-2 computation. The best way to characterize the computational cost of type-2 computation is to give a robust notion of type-2 complexity classes. In order to do so, we first study the induced topologies determined by type-2 continuous functionals of type ( N [arrow right] N ) × N [Special characters omitted.] N . Then, based on the compact sets in the induced topologies, we define a type-2 almost-everywhere relation [Special characters omitted.] over type-2 continuous functionals. The type-2 almost-everywhere relation [Special characters omitted.] provides an analogous notion of asymptotic approach for complexity analysis in type-2. We also specify a clocking scheme for OTMs based on a class of computable functions called Type-2 Time Bounds ( T 2 TB ). With the tools we developed, each type-2 time bound β ∈ T 2 TB determines a type-2 complexity class C (β). We also define a type-2 big-O notation-- O (β)--which would be a useful tool for type-2 algorithm analysis.

To justify our notion of type-2 complexity classes, we prove the Union Theorem, the Gap Theorem, the Compression Theorem, and the Speed-up Theorem in type-2 along the lines of classical complexity theory. Most of the theorems we proved are very different from their type-1 counterparts. We thus learn that the structure of type-2 complexity classes is not as sturdy as the structure in type-1; they are very sensitive to the topological constraint. With theses complexity results, we have a reasonable outlook for a general type-2 complexity theory.

#### Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

#### Recommended Citation

Li, Chung-Chih, "Type-2 complexity theory" (2001). *Electrical Engineering and Computer Science - Dissertations*. 131.

https://surface.syr.edu/eecs_etd/131

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=729114081&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD