1

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 Kaveh's brilliant formulation.]

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 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.

Community
  • 1
Steve G
  • 13
  • 4
  • 3
    I think this is a duplicate of this question. – Robin Kothari Sep 02 '12 at 01:32
  • 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 Sep 02 '12 at 08:23
  • 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 Sep 02 '12 at 13:03
  • How do you define class “NDTIME(x<n^k)”? – Tsuyoshi Ito Sep 02 '12 at 20:56
  • Sorry, NDTIME(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 Sep 02 '12 at 22:13

1 Answers1

1

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 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.

Community
  • 1
Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 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 Sep 05 '12 at 13:51
  • @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 Sep 05 '12 at 18:48
  • 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 Sep 05 '12 at 18:52
  • 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 Sep 05 '12 at 18:57
  • @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 Sep 05 '12 at 19:03
  • Note also that you need g to be time-constructible for the nondeterministic time hierarchy theorem (as far as I know). – Tsuyoshi Ito Sep 05 '12 at 19:05
  • @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 Sep 05 '12 at 19:15
  • 2
    (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 (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 Sep 05 '12 at 19:23
  • 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 Sep 06 '12 at 07:27
  • Thanks for this brilliant answer and all the illuminating comments! – Steve G Sep 18 '12 at 03:09