Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Clocking Type-2 Computation in The Unit Cost Model

Speaker: Chung-Chih Li
Slot: Array, 10:50-11:10, col. 4


In our previous works we defined a class of
functions called Type-2 Time Bounds (henceforth TB2) for
clocking the Oracle Turing Machine (henceforth OTM). In the
present paper we further advance the type-2 complexity theory
under our notion of type-2 complexity classes. We've  learned
the theory is highly sensitive to the OTM's cost model used in
dealing with the oracle answers. We present a reasonable
alternative called unit cost model, and examine how this
model shapes the outlook of the type-2 complexity theory. We prove
two theorems that are opposite to the classical union theorem and
gap theorem under our unit cost model (also opposite to the
results under another cost model in our previous works). We also
investigate some properties of TB2 including a very useful
theorem stating that there is an effective operator to convert any
$\beta \in TB2$ into an equivalent one that is 
locking-detectable}, and hence we can simplify many proofs without
loss of generality by assuming any concerned $\beta \in TB2$
locking detectable. 

websites: Arnold Beckmann 2006-07-15