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

    Identifiers