scientific article; zbMATH DE number 3992933

From MaRDI portal
Publication:4720786





[For the entire collection see Zbl 0591.00015.] We generalize the main result of \textit{W. J. Paul, N. Pippenger, E. Szemeredi} and \textit{W. T. Trotter} [On determinism and nondeterminism and related problems, FOCS, 429-438 (1983)] that deterministic linear time, L, is not equal to nondeterministic linear time, NL, to bounded oracles. Then we prove some results for linear space that are analogues of known results for polynomial space. With these facts we are able to derive some separation results for some complexity class defined by bounded oracles. Among other things, we prove that L(A), linear time with oracle A where A is complete for linear space, is strictly greater than L(A,b(n)), where b(n) is a bound on the size of the oracle tape. This will allow us to say something about the limits of self-reducibility when A is complete for linear space.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4720786)