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.