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

1 Answer 1

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.