Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-022 | 15th February 2001 00:00

On segregators, separators and time versus space



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.

ISSN 1433-8092 | Imprint