Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) (Q1094139): Difference between revisions

Let NSPACE(log n)\(<A>\) denote the class of languages accepted by nondeterministic oracle Turing machines that are restricted in the sense of Ruzzo, Simon, and Tompa. We show that it will be hard to find an oracle set A with DSPACE(log n)(A)\(=NSPACE(\log n)<A>\) since this would separate the base classes DSPACE(log n) and NSPACE(log n). This is a contrast to other types of relativizations where separation of the classes with oracle has no influence on the base classes.