View article

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 set A such that. Furthermore, there exists a computable set A 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.