A measure of relativized space which is faithful with respect to depth (Q1115190)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A measure of relativized space which is faithful with respect to depth |
scientific article |
Statements
A measure of relativized space which is faithful with respect to depth (English)
0 references
1988
0 references
A measure for relativized space is described which has the following properties. (1) \(NC_ 1\subseteq L\) relativizes. (2) Instead of \(NL\subseteq NC_ 2\) one gets \(NL\subseteq NC_ 3\) in any relativized world. (3) Savitch's theorem NSPACE(s)\(\subseteq DSPACE(s^ 2)\) relativizes. Results of this kind are not possible for the space measures used so far in the literature. The oracle machine model works as follows. The process of generating a query may be interrupted, the initial part of the query generated so far (partial query) is pushed on a stack and a more urgent query is generated. The space used by this query stack is defined to be the maximum over all steps i of the sum of the logarithms of the partial queries being on the stack on step i (for queries of length 1 the value 1 is added instead of \(0=\log 1)\).
0 references
relativizing space classes
0 references
NC hierarchy
0 references
oracle stack
0 references