From nobody@cse.Buffalo.EDU Wed Dec 30 20:53 EST 1998 From: nobody@cse.Buffalo.EDU Date: Wed, 30 Dec 1998 20:53:03 -0500 (EST) To: techreps@cse.Buffalo.EDU Subject: techrep: POST request Content-Type: text Content-Length: 1589 Comments: Test? ContactPerson: regan@cse.buffalo.edu Remote host: dynamic-b564.buf.adelphia.net Remote ident: unknown ### Begin Citation ### Do not delete this line ### %R 98-09 %U /tmp/ORT98.ps %A Ogihara, Mitusnori %A Regan, Kenneth W. %A Toda, Seinosuke %T Graded Self-Reducibility %D December 30, 1998 %I Department of Computer Science and Engineering, SUNY Buffalo %K Computational complexity, time and space complexity, self-reducibility %X We introduce two special kinds of self-reducible sets that we call {\em time-graded\/} and {\em space-graded\/} languages. Attaching time and space bounds to them yields a uniform, quantitative definition of resource-bounded self-reducibility that applies to all languages. We apply this to study the relationship between $\NSPACE[s(n)]$ and $\DSPACE[s(n)^2]$, emphasizing the case $s(n) = O(\log n)$. We show that the class of logspace-graded languages, which is contained in $\DSPACE[\log^2 n]$, contains not only $\NL$ and uniform $\NC^2$, but also a class of Aux-PDA languages that is not known to be a subclass of $\P$. We also prove that many-one space-graded classes are many-one equivalent to the special case in which the self-reduction makes one query to a string of strictly shorter length. For this latter idea of ``instance contraction,'' we note that some $\NL$-complete problems admit $n$-to-$n/2$ contraction in logspace, and prove that some $\NC^1$-complete problems are $n$-to-$n/2$ contractible by finite automata that involve only parity counting.