Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NONDETERMINISTIC TIME CLASSES:
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
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 >>>