Logical Approaches to Computational Barriers

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 that 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 |