Teilinformationsklassen sind eine Verallgemeinerung klassischer Komplexitätsklassen, bei denen Probleme nicht vollständig, sondern nur zum Teil gelöst werden. Es stellt sich heraus, daß dies in einer Reihe von Anwendungen ausreichend ist. Truth-Table-Reduktionen sind ein strukturanalytisches Hilfsmittel, das häufig verwendet wird, um die Stabilität und Kompliziertheit von Komplexitätsklassen zu quantifizieren.

Viele in der Literatur untersuchte Spielarten der Teilinformation, so zum Beispiel semirekursive, p-selektive, cheatable oder auch approximierbare Sprachen, erweisen sich als Spezialfälle der allgemeinen Definition von Teilinformation. Da Teilinformationsklassen kombinatorisch repräsentiert werden können durch sogenannte Familien, können all diese Arten von Teilinformation verglichen werden, indem man die zugehörigen Familien vergleicht. Untersuchungen der Kombinatorik von Familien im ersten Teil der Arbeit ermöglichen es, neue Resultate bezüglich der zugehörigen Teilinformationsklassen zu erhalten. Ein solches Resultat ist eine Verallgemeinerung des Generalised Non-Speedup Theorems.

Im zweiten Teil werden die Stabilität und Kompliziertheit von Teilinformationsklassen mit Hilfe von Truth-Table-Reduktionsabschlüssen untersucht. Das Hauptresultat lautet, daß solche Abschlüsse ebenfalls rein kombinatorisch beschreibbar sind. Hierdurch wird das Inklusionsproblem für Truth-Table-Abschlüsse auf endliche Kombinatorik zurückgeführt. Auch im zweiten Teil ergibt eine Analyse dieser Kombinatorik neue Resultate bezüglich der Truth-Table-Abschlüsse selbst. Unter anderem ergibt sich ein neuartiger Beiweis dafür, daß all beschränkten Reduktionsabschlüsse der p-selektiven Sprachen unterschiedlich sind.