Combining Self-reducibility and Partial Information Algorithms

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.