Timeline for Problem in computational complexity (superior class)

4 events

when toggle format	what		by	license	comment
Mar 23, 2016 at 13:39	comment	added	Yuval Filmus		The value of $n$ is allowed to depend on $M_2$. That's the order of quantifiers in the question: for every $M_2$ there is a large enough $n$. If they wanted "large enough" to be uniform, they would have switched these quantifiers.
Mar 23, 2016 at 11:47	comment	added	Sarvottamananda		Say $n=N$ is the large enough $n$ in question. Then we can construct a machine that runs $M_1$ for strings of length between $N$ and $N^2$ and any other $DTIME((1+\epsilon)n+2)$ machine for other lengths. The resulting machine is $DTIME( \max\{(1+\epsilon)n+2, N^{2.2}\})$ which is a $DTIME((1+\epsilon)n+2)$ by linear speedup theorem.
Mar 23, 2016 at 11:41	comment	added	Sarvottamananda		If $n$ is indeed independent of $M_2$ then I think it is tough to prove the propositions. At least $DTIME(n^{1.1})$ won't be superior to $DTIME( (1+\epsilon)n+2)$ by linear speedup theorem.
Mar 23, 2016 at 7:39	history	answered	Yuval Filmus	CC BY-SA 3.0