# Non-deterministic logarithmic time complexity class

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.

• You can try using the technique of padding. – Yuval Filmus May 13 '17 at 18:33
• OK, this gives me one direction (lhs implies rhs). How about the second direction? – Dudi Frid May 14 '17 at 4:00
• Only one direction of such implications is known. – Yuval Filmus May 14 '17 at 5:02
• Could you please supply me with some citation or a source? – Dudi Frid May 14 '17 at 9:57
• What computation model are you interested in? Turing machine? Random-access machine? – Yuval Filmus Sep 12 '17 at 13:04

$\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}$.