Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with near-testable:
TR95-037 | 2nd July 1995
Richard Beigel, Howard Straubing

The Power of Local Self-Reductions

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 ... more >>>

ISSN 1433-8092 | Imprint