Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$?
It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to derive a proof from this intuition.
$\begingroup$
$\endgroup$
9
-
$\begingroup$ You can try using the technique of padding. $\endgroup$– Yuval FilmusMay 13, 2017 at 18:33
-
$\begingroup$ OK, this gives me one direction (lhs implies rhs). How about the second direction? $\endgroup$– Dudi FridMay 14, 2017 at 4:00
-
1$\begingroup$ Only one direction of such implications is known. $\endgroup$– Yuval FilmusMay 14, 2017 at 5:02
-
$\begingroup$ Could you please supply me with some citation or a source? $\endgroup$– Dudi FridMay 14, 2017 at 9:57
-
1$\begingroup$ What computation model are you interested in? Turing machine? Random-access machine? $\endgroup$– Yuval FilmusSep 12, 2017 at 13:04
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
$\mathsf{DLOGTIME\subsetneq NLOGTIME}$. Search in unsorted array is a problem from $\mathsf{NLOGTIME}$, but it can't be solved deterministically in logarithmic time. This is proven. I also think that $\mathsf{NLOGTIME\not\subset DTIME}(o(n))$.
Padding argument here do not have an implication for $\mathsf P$ vs. $\mathsf{NP}$.
