Content deleted Content added
Line 81:
* I agree that formally nondeterministic algorithms don't leave choices open. But the definition given on the other site is an 80% correct explanation whereas the introduction, I remain, now still is 100% wrong.[[Special:Contributions/86.82.44.193|86.82.44.193]] ([[User talk:86.82.44.193|talk]]) 13:57, 7 July 2015 (UTC)
== You got the meaning of "nondeterministic algorithm" completely wrong ==
In the modern theory of algorithms and complexity theory the term "nondeterministic algorithm" has a very specific meaning. Nondeterministic algorithm are not opposite of deterministic one -- although the way English language works suggests so. Nondeterministic algorithm is nondeterministic in the same way as [[Non-deterministic_Turing_machine]] is, and it doesn't make any sense to speak here about "execution" or "state" of such algorithm. Because you don't execute nondeterministic Turing machines in the way you execute Python programs.
A nondeterministic TM can accept or reject an input -- the input is accepted if and only if there is a sequence of nondeterministic choices which can lead to the ACCEPT state of TM. And this definition of nondeterministic TM agrees with the way nondeterministic finite automatons, branching programs, decision trees or circuit are defined. All these different models of computation have deterministic, nondeterministic and probabilistic analogs -- and all of these are examples of nondeterministic algorithms.
You can read more about this for example Arora and Barak's complexity textbook -- http://theory.cs.princeton.edu/complexity/. To summarize, an algorithm can be of these mutually exclusive types:
* Deterministic
* Nondeterministic
* Probabilistic
* …
So nondeterministic algorithms do not include probabilistic ones.
I think the best thing to do with this article is to either just replace it with redirection to the article [[Non-deterministic_Turing_machine]], or to define here what is nondeterminism the way it is done by Arora and Barak, and give further links to articles about nondeterministic TMs, FAs, circuits and so on.
Maybe there are some other fields of CS of which I'm not aware of, and they have their own definition of nondeterminism. In this case this article probably should mention that too, but focus more on the Arora&Barak's definition of nondeterminism -- because this is what they call nondeterminism at any university course on algorithms today.
| |||