Partial information classes are relaxations of standard complexity classes where prob- lems are not solved fully but only in part, which turns out to be sufficient in a number of applications. Truth-table reductions are a tool from structural complexity theory used to quantify the stability and relative difficulty of complexity classes.
A rich variety of notions studied in the literature, including p-selective, semirecursive, cheatable and approximable languages to name a few, are special cases of the general notion of a partial information class. As partial information classes can be represented purely combinatorially by so-called families, all of the different notions of partial information can be compared by comparing families. In the first part of the thesis, the combinatorial properties of families are studied and as a consequence several new results on partial information classes are obtained, including a generalisation of the Generalised Non-Speedup Theorem.
In the second part, the stability and relative difficulty of partial information classes are analysed using truth-table reduction closures. The main result obtained is, that these closures may also be represented purely combinatorially, thus reducing the inclusion problem of truth-table closures of partial information classes to finite combinatorics. Once more, an analysis of the combinatorics yields novel results on the truth-table closures themselves. We also give a new proof that all bounded truth-table closures of the p-selective languages differ.
Part I. Combinatorial Representations of Partial Information Classes 1. Introduction to Partial Information 2. Representation of Resource Bounded Partial Information 3. Structure of Normal Families 4. Structure of Stable Families Part II. Truth-Table Closures of Partial Information Classes 5. Introduction to Reductions 6. Representation of Truth-Table Closures 7. Structure of Selective, Bottom and Top Cones 8. Structure of Cones over Families Conclusion References
