Confused about definition of a non-deterministic decider

Question

Fallowing are some definitions from book "introduction to theory of computation" by sipser.

a nondeterministic turing machine is a decider if all its computation branches halt on all input.

$NTIME(t(n)) = \{L | L \text{ is a language decided by an $O(t(n))$ time nondeterministic turing machine } \}$

What is the difference between deciding in deterministic and nondeterministic cases? why in deterministic case having a decider for language $A$ imply a decider for $\bar{A}$ but not in non-deterministic case?is it because there might be infinite number of branches ?

Answer 1

You basically have the right intuition. Let's expand the definitions one more step, to see it more clearly.

detrminstic decider: if $x\in L$, the decider will stop on YES (there is only a single branch for $x$)

non-detrminstic decider: if $x\in L$, there exists a branch on which the decider will stop on YES (there are multiple possible branches for $x$ chosen non-deterministically during the computation; some of which might be NO or non-halting).

You can state equivalent statements for any $x \not\in L$.

As you can see, there is a lot of difference between the two. It is also should be apparent why if first statement holds, the second holds as well, but not the other way.

Answer 2

Given a Turing machine, and an input $x$ written on tape:

language decision means that the Turing machine halts in one of its accepting states if $x \in L$, otherwise it halts in a rejecting state.

language acceptance means that the Turing machine halts in one of its accepting states if $x \in L$; it may loop forever otherwise.

For a deterministic Turing machine, given the current configuration, there is a unique next configuration. If $x \in L$, the deterministic Turing machine starts in one of its starting states, say $q_{start}$ with the input $x = x_1 x_2 \cdots x_n$ written on tape and follows a unique sequence of steps dictated by its deterministic transition function. This sequence of steps leads to one of the accepting states, say $q_{accept}$. Simmetrically, if $x \notin L$, the unique sequence of steps leads to one of the rejecting states, say $q_{reject}$.

In the case of a nondeterministic Turing machine, given the current configuration, there are several possible next configurations (owing to its nondeterministic transition relation: given a state and a symbol scanned, there are several choices of what to do next). This leads to an asymmetric accept/reject criterion (with regard to the deterministic case): the computation is not a chain of states (as in the deterministic case), rather it is a tree of possible computations with each path leading either to an accept or reject state. To accept a string $x$ ($x \in L$), the nondeterministic Turing machine needs to find any path along the tree leading to an accept state (one path is enough). However, in order to reject the string ($x \notin L$), it must reject an all of the paths. Regarding the computation, all paths terminate, the time used can be though of as the maximum length of paths starting from the root of the tree and the space used is the maximum number of work tape cells touched on any path starting from the root of the tree.

Note that a deterministic Turing machine is just a special case of a nondeterministic one.

Finally, in the deterministic case if one can decide a language $A$, then it can also decide its complement $\bar A$. This is exactly because of the symmetry available in the deterministic case and the asymmetry of the nondeterministic one. How to decide $\bar A$ ? Let TM be a deterministic Turing machine able to decide $A$. Then, the following deterministic Turing machine TM' decides $\bar A$: run TM on input $x$; if TM accepts, then TM' rejects and vice-versa.