Space-efficient informational redundancy

Abstract: We study the relation of autoreducibility and mitoticity for polylog-space many-one reductions and log-space many-one reductions. For polylog-space these notions coincide, while proving the same for log-space is out of reach. More precisely, we show the following results with respect to nontrivial sets and many-one reductions: [1.] polylog-space autoreducible ⇔ polylog-space mitotic, [2.] log-space mitotic ⇒ log-space autoreducible ⇒ -space mitotic, [3.] relative to an oracle, log-space autoreducible ⇏ log-space mitotic. The oracle is an infinite family of graphs whose construction combines arguments from Ramsey theory and Kolmogorov complexity. [ABSTRACT FROM AUTHOR]