期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
