__
TR01-022 | 15th February 2001 00:00
__

#### On segregators, separators and time versus space

**Abstract:**
We give the first extension of the result due to Paul, Pippenger,

Szemeredi and Trotter that deterministic linear time is distinct from

nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))

\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the

following statements holds: (1) P \neq L (2) For all constructible t,

DTIME(t) \neq NTIME(t). We also consider the problem of whether NTIME(t)

= NSPACE(t) for constructible t and show that it is related to a graph

theoretic problem - the question of whether certain families of graphs

have sublinear separators.