Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with nondeterministic time classes:
TR01-022 | 15th February 2001
Rahul Santhanam

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 ... more >>>

TR18-013 | 18th January 2018
John Hitchcock, Adewale Sekoni

Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

ISSN 1433-8092 | Imprint