A measure of relativized space which is faithful with respect to depth
作者：
Highlights：
•
摘要
It is known that NC1 ⊆ L ⊆ NL ⊆ NC2 ⊆ NC; however, known relativizations of these classes have failed to preserve these containments. These methods have failed to preserve either NC1 ⊆ L or NL ⊆ NC in the sense that one could construct oracles witnessing noncontainment. In this paper we introduce a new measure of relativized space: the oracle stack. With this measure, NC1 ⊆ L holds for all oracles, as does NL ⊆ NC3 (and NL ⊆ NC2 under certain circumstances).
论文关键词：
论文评审过程：Received 29 August 1986, Revised 6 March 1987, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(88)90031-1
