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.

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

Link to Full Text

Share

COinS