Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) (Q1094139): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:10, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) |
scientific article |
Statements
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) (English)
0 references
1987
0 references
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.
0 references
oracle Turing machines
0 references
relativizations
0 references
