Authors: Richard Beigel and Howard Straubing

Abstract: Identify a string x over {0,1} with the positive integer whose binary representation is 1x. We say that a self-reduction is k-local if on input x all queries belong to {x - 1, ... , x - k}. We show that all k-locally self-reducible sets belong to PSPACE. However, the power of k-local self-reductions changes drastically between k = 2 and k = 3. Although all 2-locally self-reducible sets belong to MOD₆PH, some 3-locally self-reducible sets are PSPACE-complete. Furthermore, there exists a 6-locally self-reducible PSPACE-complete set whose self-reduction is an m-reduction (in fact, a permutation).

We prove all these results by showing that such languages are equivalent in complexity to the problem of multiplying an exponentially long sequence of uniformly generated elements in a finite monoid, and then exploiting the algebraic structure of the monoid.

Download Full Paper