Portal de Periódicos da CAPES

Limitations on Separating Nondeterministic Complexity Classes

1981; Society for Industrial and Applied Mathematics; Volume: 10; Issue: 4 Linguagem: Inglês

10.1137/0210057

1095-7111

Charles Rackoff, Joel Seiferas,

graph theory and CDMA systems

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)$.