<p>It seems to me that you are not familiar with the basic complexity theory and therefore your question is probably not suitable for cstheory.</p>

<p>You probably mean to ask if the following statement is true:</p>

<blockquote>
  <p>$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$.</p>
</blockquote>

<p>Note that <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem#Non-deterministic_time_hierarchy_theorem" rel="nofollow noreferrer">the $\mathsf{NTime}$ hierarchy theorem</a> is tight. If the answer to your question was positive then it would separate $\mathsf{NTime}$ from $\mathsf{DTime}$ which is not known as explained in the answers to <a href="https://cstheory.stackexchange.com/q/1079/">the question linked by Robin</a>.</p>

CC BY-SA 3.0
2012-09-05T13:51:27.310Z
Let me ask you the same question: How do you define NTime(o(n^k))?  I can think of several reasonable definitions, but under any of them, I fail to see how the nondeterministic time hierarchy theorem and DTime(O(n^k))⊆NTime(o(n^k)) implies DTime(O(n^k))≠NTime(O(n^k)), maybe because I am not familiar with hierarchy theorems.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-05T18:48:59.933Z
@Tsuyoshi, right now I only remember one standard definition. Here is what I am saying, let me know if I am making a mistake: Assume $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ where $g(n+1)=o(n^k)$. Then by the hierarchy theorem, we have $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g) \subset \mathsf{NTime}(O(n^k))$. (You can object to assuming $g(n+1)=o(n^k)$ in place of $g(n)=o(n^k)$, however this is a mainly technical point, can you think of any non-artificial function $g$ s.t. $g(n+1) \in o((n+1)^k)$ but $g(n+1) \notin o(n^k)$?)
Kaveh
CC BY-SA 3.0
2012-09-05T18:52:33.813Z
ps: the first sentence was regarding the way question is stated, not the question itself. I mean have you seen anyone with basic knowledge of complexity theory write $NDTIME(x < n^k)$? Therefore it seemed to me (and still seems so) that the question is more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2012-09-05T18:57:39.720Z
I would not call “NTime(g(n)) where g(n)=o(n^k)” a valid definition of notation “NTime(o(n^k))” (or “NDTIME(x<n^k)” for that matter) because that definition obviously depends on the choice of function g(n).  I think that one of the reasonable definitions of notation “NTime(o(n^k))” is the union of classes NTime(g(n)) over all such g(n), but under this definition, we (at least I) cannot use the nondeterministic time hierarchy theorem to get your claim.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-05T19:03:18.467Z
@Tsuyoshi, I see, your definition is also reasonable (maybe the more standard one), however that was not what I meant and it is not unusual to write $o(f)$ for an arbitrary function in $o(f)$ (I think there was a question about how to read the asymptotic notations on [math.se].) But I will edit the answer to remove the ambiguity.
Kaveh
CC BY-SA 3.0
2012-09-05T19:05:07.013Z
Note also that you need g to be time-constructible for the nondeterministic time hierarchy theorem (as far as I know).
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-05T19:15:22.247Z
@Tsuyoshi, $g$ in the statement of the hierarchy theorem is $n^k$ which is time-constructible. ps: It seems to me that the argument would also holds for the union definition if $\mathsf{DTime}(n^k)$ has a complete problem under linear-time reductions (which if I am not mistaken seems to be the case).
Kaveh
CC BY-SA 3.0
2012-09-05T19:23:03.530Z
(1) Oops, I did not know that we do not need need time-constructibility for the smaller bound in the nondeterministic time hierarchy theorem!  (2) I quickly checked [Seiferas, Fischer, and Meyer JACM 1978](http://dx.doi.org/10.1145/322047.322061) (which I should have probably done earlier), and I agree, the original statement (see Theorem 4 and Corollary 4.1) seems to be the union version instead of the proper inclusion for every g.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-06T07:27:51.453Z
No need for big-Oh inside DTIME and the like. Also rather than discussing unconventional notation, why don't we just untangle the question. I have no doubt in my mind OP is asking "does there exist a function $g$ such that $g \in o(n^k)$ and $\mathsf{DTIME}(n^k) \subseteq \mathsf{NDTIME}(g(n))$.
Sasho Nikolov
CC BY-SA 3.0
2012-09-18T03:09:13.003Z
Thanks for this brilliant answer and all the illuminating comments!
Steve G
CC BY-SA 3.0
2012-09-04T17:46:25.830Z
2012-09-05T19:04:14.097Z
2017-04-13T12:32:28.053Z
Kaveh
<p>Can this statement be confirmed or disproved:</p>

<blockquote>
  <p>$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$</p>
</blockquote>

<p>[Question changed to use <a href="https://cstheory.stackexchange.com/a/12503/10576">Kaveh's brilliant formulation</a>.]</p>

<p>Here the NDTM must "outrun" the DTM.</p>

<p>This seems similar to the PvNP question, but I'm not sure...</p>

<p>Thanks!</p>

<p>EDIT: This question seeks an inequality between the run time of polytime DTM deciders and their corresponding NP verifiers. If k=1, the proposition fails (e.g.: determining <a href="http://en.wikipedia.org/wiki/Parity_function" rel="nofollow noreferrer">parity</a> requires n steps on a TM and therefore a verifier cannot take any shortcuts). But if k>=2 ...?</p>

<p>I wonder if the statement can be disproved without leading to any major or unexpected complexity class separations... Is there a diagonalization argument that could work here.</p>

CC BY-SA 3.0
2012-09-02T01:32:04.333Z
I think this is a duplicate of [this question](http://cstheory.stackexchange.com/q/1079/).
Robin Kothari
CC BY-SA 3.0
2012-09-02T08:23:07.350Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Note that there is also [cs.se] which has a broader scope. ps: I agree with Robin, it seems that the answers to the question linked by Robin should answer yours.
Kaveh
CC BY-SA 3.0
2012-09-02T13:03:17.183Z
Hmm, this asks if DTIME(n^k) is a subset of NDTIME(x<n^k). The other question asks if DTIME(n^k) is equivalent to NDTIME(n^k). For example, P is in NP, but the equivalence (P=NP) is a different question.
Steve G
CC BY-SA 3.0
2012-09-02T20:56:20.583Z
How do you define class “NDTIME(x<n^k)”?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-02T22:13:08.710Z
Sorry, [NDTIME](http://en.wikipedia.org/wiki/NTIME)(f(n)) where f(n) << n^k. A DTM that runs in O(n^3) and a corresponding NP verifier that runs in O(n) would be consistent with the conjecture...
Steve G
<cc.complexity-theory><time-complexity><np>
$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?
Steve G
# $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?

(Asked by: username_0 on 2012-09-02)

Can this statement be confirmed or disproved:

> $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$

[Question changed to use [username_2's brilliant formulation](https://cstheory.stackexchange.com/a/12503/10576).]

Here the NDTM must "outrun" the DTM.

This seems similar to the PvNP question, but I'm not sure...

Thanks!

EDIT: This question seeks an inequality between the run time of polytime DTM deciders and their corresponding NP verifiers. If k=1, the proposition fails (e.g.: determining [parity](http://en.wikipedia.org/wiki/Parity_function) requires n steps on a TM and therefore a verifier cannot take any shortcuts). But if k>=2 ...?

I wonder if the statement can be disproved without leading to any major or unexpected complexity class separations... Is there a diagonalization argument that could work here.

**Tags:** cc.complexity-theory, time-complexity, np

> **Comments:**
> **username_1**: I think this is a duplicate of [this question](http://cstheory.stackexchange.com/q/1079/).  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Note that there is also [cs.se] which has a broader scope. ps: I agree with Robin, it seems that the answers to the question linked by Robin should answer yours.  
> **username_0**: Hmm, this asks if DTIME(n^k) is a subset of NDTIME(x<n^k). The other question asks if DTIME(n^k) is equivalent to NDTIME(n^k). For example, P is in NP, but the equivalence (P=NP) is a different question.  
> **username_3**: How do you define class “NDTIME(x<n^k)”?  
> **username_0**: Sorry, [NDTIME](http://en.wikipedia.org/wiki/NTIME)(f(n)) where f(n) << n^k. A DTM that runs in O(n^3) and a corresponding NP verifier that runs in O(n) would be consistent with the conjecture...  

---

## 1 answers

### Answer by username_2 on 2012-09-04. Score: 1 | Accepted answer

It seems to me that you are not familiar with the basic complexity theory and therefore your question is probably not suitable for cstheory.

You probably mean to ask if the following statement is true:

> $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$.

Note that [the $\mathsf{NTime}$ hierarchy theorem](http://en.wikipedia.org/wiki/Time_hierarchy_theorem#Non-deterministic_time_hierarchy_theorem) is tight. If the answer to your question was positive then it would separate $\mathsf{NTime}$ from $\mathsf{DTime}$ which is not known as explained in the answers to [the question linked by Robin](https://cstheory.stackexchange.com/q/1079/).

> **Comments:**
> **username_3**: Let me ask you the same question: How do you define NTime(o(n^k))?  I can think of several reasonable definitions, but under any of them, I fail to see how the nondeterministic time hierarchy theorem and DTime(O(n^k))⊆NTime(o(n^k)) implies DTime(O(n^k))≠NTime(O(n^k)), maybe because I am not familiar with hierarchy theorems.  
> **username_2**: @Tsuyoshi, right now I only remember one standard definition. Here is what I am saying, let me know if I am making a mistake: Assume $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ where $g(n+1)=o(n^k)$. Then by the hierarchy theorem, we have $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g) \subset \mathsf{NTime}(O(n^k))$. (You can object to assuming $g(n+1)=o(n^k)$ in place of $g(n)=o(n^k)$, however this is a mainly technical point, can you think of any non-artificial function $g$ s.t. $g(n+1) \in o((n+1)^k)$ but $g(n+1) \notin o(n^k)$?)  
> **username_2**: ps: the first sentence was regarding the way question is stated, not the question itself. I mean have you seen anyone with basic knowledge of complexity theory write $NDTIME(x < n^k)$? Therefore it seemed to me (and still seems so) that the question is more suitable for [cs.se].  
> **username_3**: I would not call “NTime(g(n)) where g(n)=o(n^k)” a valid definition of notation “NTime(o(n^k))” (or “NDTIME(x<n^k)” for that matter) because that definition obviously depends on the choice of function g(n).  I think that one of the reasonable definitions of notation “NTime(o(n^k))” is the union of classes NTime(g(n)) over all such g(n), but under this definition, we (at least I) cannot use the nondeterministic time hierarchy theorem to get your claim.  
> **username_2**: @Tsuyoshi, I see, your definition is also reasonable (maybe the more standard one), however that was not what I meant and it is not unusual to write $o(f)$ for an arbitrary function in $o(f)$ (I think there was a question about how to read the asymptotic notations on [math.se].) But I will edit the answer to remove the ambiguity.  
> **username_3**: Note also that you need g to be time-constructible for the nondeterministic time hierarchy theorem (as far as I know).  
> **username_2**: @Tsuyoshi, $g$ in the statement of the hierarchy theorem is $n^k$ which is time-constructible. ps: It seems to me that the argument would also holds for the union definition if $\mathsf{DTime}(n^k)$ has a complete problem under linear-time reductions (which if I am not mistaken seems to be the case).  
> **username_3**: (1) Oops, I did not know that we do not need need time-constructibility for the smaller bound in the nondeterministic time hierarchy theorem!  (2) I quickly checked [Seiferas, Fischer, and Meyer JACM 1978](http://dx.doi.org/10.1145/322047.322061) (which I should have probably done earlier), and I agree, the original statement (see Theorem 4 and Corollary 4.1) seems to be the union version instead of the proper inclusion for every g.  
> **username_4**: No need for big-Oh inside DTIME and the like. Also rather than discussing unconventional notation, why don't we just untangle the question. I have no doubt in my mind OP is asking "does there exist a function $g$ such that $g \in o(n^k)$ and $\mathsf{DTIME}(n^k) \subseteq \mathsf{NDTIME}(g(n))$.  
> **username_0**: Thanks for this brilliant answer and all the illuminating comments!  

---

