TR95-037 Authors: Richard Beigel, Howard Straubing

Publication: 6th July 1995 16:35

Downloads: 2010

Keywords:

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.