On separators, segregators and time versus space

Gives an extension of the result due to Paul, Pippenger, Szemeredi and Trotter (1983) that deterministic linear time (DTIME) is distinct from nondeterministic linear time (NTIME). We show that NTIME[n√log*(n)] ≠ DTIME[n√log*(n)]. We show that if the class of multi-pushdown graphs has {o(n), o[n/log(n)]} segregators, then NTIME[n log(n)] ≠ DTIME[n log(n)]. We also show that at least one of the following facts holds: (1) P ≠ L, and (2) for all polynomially bounded constructible time bounds t, NTIME(t) ≠ DTIME(t). We consider the problem of whether NTIME(t) is distinct from NSPACE(t) for constructible time bounds t. A pebble game on graphs is defined such that the existence of a “good” strategy for the pebble game on multi-pushdown graphs implies a “good” simulation of nondeterministic time-bounded machines by nondeterministic space-bounded machines. It is shown that there exists a “good” strategy for the pebble game on multi-pushdown graphs if the graphs have sublinear separators. Finally, we show that nondeterministic time-bounded Turing machines can be simulated by Σ₄ machines with an asymptotically smaller time bound, under the assumption that the class of multi-pushdown graphs has sublinear separators