scientific article; zbMATH DE number 3992933
[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.
- Complexity classes and sparse oracles
- Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
- scientific article; zbMATH DE number 3978383
- On sparse oracles separating feasible complexity classes
- scientific article; zbMATH DE number 223337
- scientific article; zbMATH DE number 515747
- A general method to construct oracles realizing given relationships between complexity classes
- Polynomial-time random oracles and separating complexity classes
- scientific article; zbMATH DE number 139642
- Complexity, combinatorial group theory and the language of palutators
- Relativized alternation and space-bounded computation
- A note on the density of oracle decreasing time-space complexity
- Complexity classes and sparse oracles
- Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
- scientific article; zbMATH DE number 4045155 (Why is no real title available?)
- On quasilinear-time complexity theory
- Simulating time with square-root 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)