patternMinor
Confused about definition of a non-deterministic decider
Viewed 0 times
definitionnondeciderconfuseddeterministicabout
Problem
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 ?
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 ?
Solution
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.
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.
Context
StackExchange Computer Science Q#142007, answer score: 2
Revisions (0)
No revisions yet.