1
$\begingroup$

I understood that a NTM can say only yes but it doesn't know if the input is a NO instance with a single execution. Furthermore, the NTM can diverges and, at the same time, can decide a language (source: Papadimitrou - Computational Complexity, proposition 7.1). While a TM must converges in a "yes" or "no" answer to decide the same language. Now, we know that for a NTM that decides a language L we can create a TM that decides L (theorem 2.6). But suppose that the NTM diverges for some computation. How can the TM treat this case?

[EDIT] Definition (source Papadimitrou, pg 45): A non-deterministc Turing Machine decides a language L if for any input x, the following is true: x belongs to L iff there is an acceptance path.

This definition admits machines that, instead of rejecting an input, diverge and at the same time decide a language.

Theorem 2.6 (pg 47): Suppose that language L is decided by a nondeterministic Turing machine N. Then it is decided by a deterministic Turing machine M.

Proposition 7.1 (pg 141): Suppose that a (deterministic or nondeterministic) Turing machine M decides a language L within time (or space) f(n), where f is a proper function. Then there is a precise Tring machine M', which decides the same language in time (or space, respectively). O(f(n)).

This last proposition confirms that there is a Turing machine that decides a language and that diverges for some path.

|cite|improve this question
$\endgroup$
2
$\begingroup$

If we're only interested in computability, and not in the resources used by the computation (i.e., complexity), then we can simulate an NTM as follows. First, simulate every possible sequence of nondeterministic choices for one step. Then, start again and do them all for two steps. Then, start again and do them all for three steps, and so on.

There are three possible results of this simulation.

  1. If any of the simulated computations accepts (so, in particular, it terminates), then we accept. In this case, it doesn't matter if some other computations would diverge.

  2. If no computation accepts but, after some number of steps, all computations have rejected, we reject.

  3. If no computation accepts and at least one computation diverges, then the simulation will also diverge.

This is a faithful simulation of the nondeterministic machine. If some computation path accepts, we accept, and this is the definition of acceptance for nondeterministic machines. If every computation path halts and rejects, we reject, as we should. Otherwise, we diverge, as does the nondeterministic machine.

However, the case you're looking at does include resource bounds. Papadimitriou is essentially comparing two different notions of the resources used by an NTM and showing that they're both the same. I'll talk about time for concreteness, but the same arguments apply to space. One way of defining $\mathrm{NTIME}(f(n))$ would be to say that every possible computation path must run within $f(n)$ steps, and the other would be to say that only the accepting paths need to. However, because we're only interested in constructible functions $f$, we can use the following idea to make the two notions identical. First, the machine deterministically computes $f(n)$ and then it does the nondeterministic computation, counting off the steps. If the step counter reaches $f(n)$, and the machine hasn't accepted, we must be either on a rejecting path or a diverging one. In either case, the path won't accept, so we can reject. Therefore, any language that's accepted by an NTM where every accepting path uses at most $f(n)$ steps is also decided by an NTM where every path uses at most $f(n)$ steps and no path diverges.

Technically, I've only shown that we can do it in something like $3f(n)$ steps, but the linear speed-up theorem says we can get rid of the constant $3$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for answer! I agree with this reasoning but let's focus on the third case: an NTM that diverges for some input still can decides L. But when we going to simulate it, the TM accepts the language instead deciding it, contraddicting the statement (theorem 2.6). $\endgroup$ – Daniele Cuomo Sep 2 '18 at 7:41
  • $\begingroup$ I dispute that a machine that diverges in this sense can be said to decide any language. I don't have my copy of Papadimitriou's book with me at the moment but I believe it's generally accurate, so I suspect you've misunderstood something. Could you include the relevant theorem statements, definitions, etc. in your question? $\endgroup$ – David Richerby Sep 2 '18 at 7:43
  • $\begingroup$ I suspect too, anyway I included the statements. $\endgroup$ – Daniele Cuomo Sep 2 '18 at 8:09
  • $\begingroup$ @Daniel-san Does my edit clear things up? $\endgroup$ – David Richerby Sep 2 '18 at 8:25
  • $\begingroup$ Yes, partially. But in the proof of theorem 2.6 the book doesn't use a counter (it also affirms that it has no knowledge of the bounds f (n)). Towards the end of the proof, it explains how he handles the rejection case, but it assumes that all computations halt in time f (n), which is not always true. If instead we assume that it is always true, we could use a DFS simulation instead of BFS, but, again, it affirms that it must be done necessarily with a BFS approach. $\endgroup$ – Daniele Cuomo Sep 2 '18 at 9:58
1
$\begingroup$

A nondeterministic Turing machine accepts an input iff there is at least one accepting path, that is, one set of guesses for which the machine accepts. A path on which the machine diverges is not an accepting path.

We are often interested in time-constraint nondeterministic Turing machines. Such Turing machines always halt, on every computation path. This is the case for nondeterministic polytime Turing machines, the machine model corresponding to the famous complexity class $\mathsf{NP}$.

|cite|improve this answer
$\endgroup$

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.