At the beginning of this paper, the author notes that a number of open questions deal with nondeterminism and with the relationship between log space and polynomial time. Over the past 15 years, a succession of seemingly contradictory results have appeared on whether the use of oracles would shed some light on these issues. In some cases, inclusions at the base level remained true when they were relativized to models with oracles, while in other cases the exact opposite was true. For example, an oracle D exists such that a simpler class (NL, which is nondeterministic log space) with that oracle D was shown to contain a larger class (P) with that same oracle.
In an attempt to make some sense out of this chaotic situation, Toda considers tally sets (that is, languages over the single-letter alphabet {1}). The first part of the main result of the paper shows that deterministic log space (DL) is equal to nondeterministic log space if and only if DLT = NLT for all tally sets T. Similar results hold for the relationship between DL (or NL) and P (or NP). The final section of the paper gives some similar results (using a slightly restricted form of access to the oracle) for space-bounded classes of machines.
The paper is well written, and the author is meticulous in spelling out exactly which complexity classes, which type of machines, and so on will be discussed. The author is also very gracious in acknowledging the contributions of an anonymous referee.
