科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 (logn " log log n)-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.
- 出版日期2010-12
