Relativization of questions about log space computability |
| |
| Authors: | Richard E Ladner Nancy A Lynch |
| |
| Affiliation: | (1) Department of Computer Science, University of Washington, 98195 Seattle, Washington, USA;(2) Department of Mathematics, University of Southern California, 90007 Los Angeles, California, USA |
| |
| Abstract: | A notion of log space Turing reducibility is introduced. It is used to define relative notions of log space,
A
, and nondeterministic log space,
. These classes are compared with the classes
and
which were originally defined by Baker, Gill, and Solovay BGS]. It is shown that there exists a computable setA such that
. Furthermore, there exists a computable setA such that
and
. Also a notion of log space truth table reducibility is defined and shown to be equivalent to the notion of log space Turing reducibility.Research supported by NSF Grant No. GJ 43264.Research supported by NSF Grant No. DCR 92373. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
