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

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

CC BY-SA 4.0
2019-08-08T01:56:31.423Z
2019-08-08T02:04:44.383Z
2019-08-08T02:04:44.383Z
Matthew Allbee
<p>Recently I've seen <a href="https://i.sstatic.net/qOhy2.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qOhy2.gif" alt="enter image description here"></a> inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it?</p>

<p>Also, the paper shows that the misinformation containment problem cannot be approximated within a factor of <a href="https://i.sstatic.net/KFSpa.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KFSpa.gif" alt="enter image description here"></a> in polynomial time unless <a href="https://i.sstatic.net/cnRqE.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/cnRqE.gif" alt="enter image description here"></a>. Can you explain this sentence more clearly?</p>

<p>Here's a link to the paper, for more information:
<a href="http://papers.nips.cc/paper/7317-on-misinformation-containment-in-online-social-networks" rel="nofollow noreferrer">http://papers.nips.cc/paper/7317-on-misinformation-containment-in-online-social-networks</a>  </p>

<complexity-classes><time-complexity><randomized-algorithms>
what does NP ⊆ DTIME(...) mean?
Reihaneh Hassanzadeh
# what does NP ⊆ DTIME(...) mean?

(Asked by: username_0 on 2019-08-07)

Recently I've seen [![enter image description here](https://i.sstatic.net/qOhy2.gif)](https://i.sstatic.net/qOhy2.gif) 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](https://i.sstatic.net/KFSpa.gif)](https://i.sstatic.net/KFSpa.gif) in polynomial time unless [![enter image description here](https://i.sstatic.net/cnRqE.gif)](https://i.sstatic.net/cnRqE.gif). 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>

**Tags:** complexity-classes, time-complexity, randomized-algorithms

---

## 1 answers

### Answer by username_1 on 2019-08-08. Score: 2

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


---

