Self-reducibility (Q2639637)

In the paper the ldq-self reducibility, wdq-self reducibility, and logspace self-reducibility are defined (ldq stands for length-decreasing queries and wdq for word-decreasing queries). The properties derived from the definitions regarding the interconnection between uniform and nonuniform complexity classes are used to prove known results and to obtain new ones regarding deterministic time classes, nondeterministic space classes and reducibility to context-free languages. From new results obtained here, we remark the following: i) Let A be a logspace self-reducible set. If A \(\in NLOG/\log\) then A \(\in NLOG;\) ii) Let M be a pushdown automaton with no \(\lambda\)-transition which accepts by empty store. There is a set A \(\in LOG(CFL)\) which is logspace self-reducible such that L(M) \(\in DLOG(A)\). Furthermore, if M is deterministic then A \(\in LOG(DCFL)\).