Clocking type-2 computation in the unit cost model

Abstract. In [12] we defined a class of functions called Type-2 Time Bounds (henceforth T2TB) for clocking the Oracle Turing Machine (OTM) in order to capture the long missing notion of complexity classes at type-2. In the present paper we further advance the type-2 complexity theory under our notion of type-2 complexity classes. We have learned that the theory is highly sensitive to how the oracle answers are handled. We present a reasonable alternative called unit cost model, and examine how this model shapes the outlook of the type-2 complexity theory. Under the unit cost model we prove two theorems opposite to the classical union theorem and gap theorem. We also investigate some properties of T2TB including a very useful theorem stating that there is an effective operator to convert any β ∈ T2TB into an equivalent one that is locking-detectable. The existence of such operator allows us to simplify many proofs without loss of generality. 1