### Tantau, Till

Technische Universität Berlin

Berlin, Germany, 1999

## Combinatorial Representations of Partial Information Classes and their Truth-Table Closures

### Abstract

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.

### Table of Contents

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