Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-022 | 15th February 2001 00:00

On segregators, separators and time versus space

RSS-Feed

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.



ISSN 1433-8092 | Imprint