**Abstract**

A language L is self-reducible if for every word w, the question “w ∈ L?” can be reduced in polynomial time to questions “q ∈ L?” such that every word q is smaller than w. For example, most NP-complete languages are self-reducible.

A partial information algorithm for a language L computes in polynomial time partial information about the membership of its input words in L. Such algorithms are classified depending on the type of partial information they compute. In the literature, languages with many interesting types of partial information algorithms have been studied extensively, for example p-selective, strongly membership comparable, p-cheatable and easily countable languages.

Buhrman, van Helden, and Torenvliet showed that the languages in P can be characterized as self-reducible p-selective languages. We show that this also holds for languages with other types of partial information algorithms. For example, this holds for easily 2-countable languages and languages which are strongly 2-membership comparable as well as its complement. On the other hand, we discuss whether there are self-reducible languages that are not in P and have partial information algorithms.

1 Introduction1.1 Contributions of the Thesis 1.2 Structure of the Thesis 1.3 Basic Definitions and Notation2 Preliminaries from Complexity Theory2.1 Turing Machines and Complexity Classes 2.2 Relativized Computation 2.3 Reducibilities 2.3.1 Many-One and Turing Reducibility 2.3.2 Truth-Table, Positive, and Bounded Reducibilities 2.3.3 Hardness, Completeness, and Reduction Closures 2.4 Self-Reducibilities 2.4.1 Introduction to Self-Reducibility 2.4.2 Examples of Self-Reducible Languages 2.4.3 Complexity of Self-Reducible Languages3 Partial Information3.1 Pools, Families, and Classes 3.2 Basic Families 3.2.1 SIZE-Families 3.2.2 CHEAT-Families 3.2.3 SEL-Families 3.2.4 CARD- and NONSEL-Families 3.3 Normal Forms 3.4 Inclusion Structure4 Reduction Closures of Partial Information Classes4.1 Closure under Basic Reducibilities 4.2 Closure under Positive Reducibilities 4.3 Converting Turing into Truth-Table Reductions 4.3.1 Binary Trees as Languages, Embeddings, and Rank 4.3.2 Bounding the Rank in Terms of Pools 4.3.3 Proof of the Theorem5 Combining Self-Reducibility and Partial Information5.1 Converting Turing into Truth-Table Self-Reductions 5.2 Self-Reducible Partial Information Languages that are in P 5.2.1 Self-Reducible Languages in P[SMC_{2}\cap COSMC_{2}] are in P 5.2.2 Self-Reducible Languages in P[NONSEL_{2}] are in P 5.2.3 Results for Disjunctive and Conjunctive Self-Reducibilities 5.3 Can Self-Reducible Partial Information Languages be not in P?6 Conclusion6.1 Summary of Main Results 6.2 Open Questions and Conjectures