Recently I've seen enter image description here inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it?

Also, the paper shows that the misinformation containment problem cannot be approximated within a factor of enter image description here in polynomial time unless enter image description here. Can you explain this sentence more clearly?

Here's a link to the paper, for more information: http://papers.nips.cc/paper/7317-on-misinformation-containment-in-online-social-networks


$DTIME$ is deterministic time complexity, or the time complexity of a problem in reference to a Deterministic Turing Machine. If a problem can be solved in $\mathcal{O}(f(n))$ on a determininistic turing machine, then it is in $DTIME(f(n))$. Saying that $NP \subseteq DTIME(n^{poly log n})$ is equivalent to saying that $NP$ is within the set of problems that can be solved within $\mathcal{O}(n^{poly log n})$ on a deterministic turing machine. I'd like to point out that it is not known whether this is true, though.

The sentence you referenced is saying that the misinformation containment problem can be approximated in polynomial time, within a factor of $\Omega(2^{log^{1-\epsilon}|m|^4})$ of the optimal solution, unless $NP \subseteq DTIME(n^{poly log n})$.


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.