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 Introduction
  1.1 Contributions of the Thesis
  1.2 Structure of the Thesis
  1.3 Basic Definitions and Notation

2 Preliminaries from Complexity Theory
  2.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 Languages

3 Partial Information

  3.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 Structure

4 Reduction Closures of Partial Information Classes
  4.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 Theorem

5 Combining Self-Reducibility and Partial Information
  5.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[SMC2 \cap COSMC2] are in P
      5.2.2 Self-Reducible Languages in P[NONSEL2] 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 Conclusion
  6.1 Summary of Main Results
  6.2 Open Questions and Conjectures