Rahul Santhanam

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

John Hitchcock, Adewale Sekoni

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