1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.