Limitations on Separating Nondeterministic Complexity Classes

Charles Rackoff, Joel Seiferas · SIAM Journal on Computing · 1981

If the time bounds defining two nondeterministic complexity classes are too close for separation by the two known techniques, then they are almost too close for separation by any relativizable technique. Proof of an analogous result for space would be a major breakthrough, implying $\operatorname{NSPACE}(\log n) = \operatorname{DSPACE}(\log n)$.

Read the paper · More papers on PaperTik