0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I think this is a duplicate of this question. $\endgroup$
    – Robin Kothari
    Sep 2 '12 at 1:32
  • $\begingroup$ 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 Computer Science which has a broader scope. ps: I agree with Robin, it seems that the answers to the question linked by Robin should answer yours. $\endgroup$
    – Kaveh
    Sep 2 '12 at 8:23
  • $\begingroup$ 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. $\endgroup$
    – Steve G
    Sep 2 '12 at 13:03
  • $\begingroup$ How do you define class “NDTIME(x<n^k)”? $\endgroup$
    – Tsuyoshi Ito
    Sep 2 '12 at 20:56
  • $\begingroup$ 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... $\endgroup$
    – Steve G
    Sep 2 '12 at 22:13
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Sep 5 '12 at 13:51
  • $\begingroup$ @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)$?) $\endgroup$
    – Kaveh
    Sep 5 '12 at 18:48
  • $\begingroup$ 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 Computer Science. $\endgroup$
    – Kaveh
    Sep 5 '12 at 18:52
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Sep 5 '12 at 18:57
  • 2
    $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Sep 5 '12 at 19:23

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.