__Technical report.:__

** Samuel R. Buss and Stephen A. Cook and Patrick W. Dymond and
Louise Hay.
"The log space oracle hierarchy collapses."
Technical report #CS87-103. Computer Science Engineering
Department, Univ. of California, San Diego. 1987.**

**This was never published since the results were out-of-date almost immediately
after we did the work.**

** Download article: postscript or PDF. **

** Abstract: **The polynomial time hierarchy of Meyer
and Stockmeyer has several equivalent characterizations --- in particular it can be
defined either in terms of polynomial time oracle Turing machines \cite{Sto76}, or in
terms of polynomial time alternating Turing machines where the number of alternations is
finitely bounded \cite{CKS}. One of the most important open questions in the area is
whether or not this hierarchy collapses. (It collapses to $P$ iff $P = NP$.) Similar
hierarchies based on space bounded computations have been investigated by Ruzzo, Simon and
Tompa \cite{RST}. They introduced a well-behaved model of space-bounded oracle Turing
machine, and showed that the entire log space alternation hierarchy was contained in the
second level of the log space oracle hierarchy. %$\LNL$, the class of sets accepted by
%deterministic log space oracle Turing machines with %an oracle from $NSPACE(\log n)$.
Subsequently Lange, Jenner and Kirsig \cite{LJK} proved that the alternation hierarchy
collapsed to its second level; this suggested the possibility that the log space oracle
hierarchy might not coincide with the log space alternation hierarchy. In this paper we
show that the log space oracle hierarchy also collapses, that it thus does coincide with
the log space alternation hierarchy, and that the resulting complexity class $\LNL$ has
other interesting characterizations in terms of circuits with oracle gates.

**Back to Sam Buss's publications page.**