Graded Self-Reducibility
Kenneth W. Regan, Mitusnori Ogihara, Seinosuke Toda · 1998
We introduce two special kinds of self-reducible sets that we call time-graded and 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 n], contains not only NL and uniform NC, 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-complete problems are n-to-n/2 contractible by finite automata that involve only parity counting. 1 Time and Space Graded Languages A language Z is autoreducible if there is an oracle Turing machine M such that for all x, M(x) decides whether x ∈ Z without querying x itself. Placing time and/or space bounds (etc.) on M , and perhaps imposing standard truth-table, disjunctive, conjunctive, many-one (etc.) restrictions on the way M treats its queries, together define kinds of autoreductions. A self-reduction is the special case where all queries y made by M(x) are below x in some partial order. Complexity-bounded self-reductions are commonly defined by placing conditions on the partial order as well as on M . These two concepts—mostly the latter, recently the former—have had wide importance and application in complexity theory. ∗Supported by a US-Japan Co-operative Research grant from the National Science Foundation, NSF Grant INT-9726724. Also partly supported by NSF Grants CCR-9701911 and CCR-9725021. †Also partly supported by NSF grant INT-9726724. Corresponding author—contact: [email protected] ‡Also partly supported by NSF grant INT-9726724