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.