ECCC-Report TR01-022https://eccc.weizmann.ac.il/report/2001/022Comments and Revisions published for TR01-022en-usThu, 08 Mar 2001 11:26:14 +0200
Paper TR01-022
| On segregators, separators and time versus space |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2001/022We 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.
Thu, 08 Mar 2001 11:26:14 +0200https://eccc.weizmann.ac.il/report/2001/022