Combining Self-reducibility and Partial Information Algorithms

Abstract A partial information algorithm for a language A computes, for some fixed m, for input words x 1, .. ., x m a set of bitstrings containing χ A ( x 1, .. ., x m ). E. g. , p-selective, approximable, and easily countable languages are defined by the existence of polynomial-time partial information algorithms of specific type. Self-reducible languages, for different types of self-reductions, form subclasses of PSPACE. For a self-reducible language A, the existence of a partial information algorithm sometimes helps to place A into some subclass of PSPACE. The most prominent known result in this respect is: P-selective languages which are self-reducible are in P [9]. Closely related is the fact that the existence of a partial information algorithm for A simplifies the type of reductions or self-reductions to A. The most prominent known result in this respect is: Turing reductions to easily countable languages simplify to truth-table reductions[8]. We prove new results of this type. We show: 1 Self-reducible languages which are easily 2-countable are in P. This partially confirms a conjecture of [8]. 2 Self-reducible languages which are (2 m – 1, m )-verbose are truth-table self-reducible. This generalizes the result of [9] for p-selective languages, which are ( m + 1, m )-verbose. 3 Self-reducible languages, where the language and its complement are strongly 2-membership comparable, are in P. This generalizes the corresponding result for p-selective languages of [9]. 4 Disjunctively truth-table self-reducible languages which are 2-membership comparable are in UP. Topic: Structural complexity.

Authors

• André Hernich
• Arfst Nickelsen

Keywords

No keywords are indexed for this paper.