For completeness, sublogarithmic space is no space |
| |
| Authors: | Manindra Agrawal |
| |
| Affiliation: | Department of Computer Science, Indian Institute of Technology, Kanpur 208016, India |
| |
| Abstract: | It is shown that for any class C closed under linear-time reductions, the complete sets for C under sublogarithmic reductions are also complete under 2DFA reductions, and thus are isomorphic under first-order reductions. |
| |
| Keywords: | Isomorphisms Completeness Sublogarithmic reductions Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
