The complexity types of computable sets

摘要

We analyze the fine structure of time complexity classes for RAMS, in particular the equivalence relation A = cB (“A and B have the same time complexity”) ⇔ (for all time constructible f: A ϵ DTIME(f) ⇔ B ϵ DTIME(f)). The = c-equivalence class of A is called its complexity type. Characteristic sequences of time bounds are introduced as a technical tool for the analysis of complexity types. We investigate the relationship between the complexity type of a set and its polynomial time degree, as well as the structure of complexity types inside P with regard to linear time degrees. Furthermore, it is shown that every complexity type contains a sparse set and that the complexity types with their natural partial order form a lattice.