A note on relativized log space |
| |
| Authors: | Walter J. Savitch |
| |
| Affiliation: | (1) Department of Electrical Engineering and Computer Sciences, University of California, San Diego, La Jolla, California, USA |
| |
| Abstract: | It is shown that there is a recursive oracleD such that, thereby answering an open question of Ladner and Lynch [5]. Here and denote the class of languages accepted in deterministic, respectively nondeterministic, space logn.This work was supported by NSF Grant MCS-8001963. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
