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 MOD6PH, 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.