Talk:Nondeterministic algorithm: Difference between revisions

Revision as of 21:10, 6 July 2015

Revision as of 21:11, 6 July 2015

Line 72:

* This is how it was explained in the formal languages course I took as a student: a nondeterministic algorithm is not an algorithm that makes choices, but one that leaves choices open. It has at least one explicit choice point for which the decision which of the available options to take is ''left open'', i.e. not made by the algorithm, and while running, ''any'' of the available options may be taken. It is ''not'' the case that the algorithm always magically decides on an optimal choice. Now a string is said to be accepted by a nondeterministic algorithm or device if there is at least one possible run, i.e. at least one particular set of choices for every choice point encountered during runs, such that the final result is to accept the string. As it was explained to me, this is not a property of nondeterministic algorithms as such, but only of how they are applied in defining nondeterministic acceptance of languages. So quicksort in which some choice point, e.g. the choice of how to partition, is left open in this way, is indeed a nondeterministic algorithm. I do agree that it is confusing to mention a sorting algorithm as an example, because the relationship between such an algorithm and its intended results (a sorted input string) is completely different from the relationship between a nondeterministic string accepting algorithm and its intended result (acceptance or nonacceptance of the input string). [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 21:10, 6 July 2015 (UTC)

* I don't think the above descriptions are improvements. Calling the options at a choice point "steps" is confusing to me because it suggests to me that they are made in sequence instead of being alternatives. Saying that "on different runs the choices made may differ" is correct but not strong enough: it is essential that whenever a choice is left open, ''any'' of the available options can be taken during a run. Saying that a deterministic sorting algorithm "simply chooses the right sorting sequence" or that a nondeterministic algorithm doesn't avehave a direct computational algorithm doesn't make sense to me. Providing a definition as if it has ''no'' computational interpretation would completely miss the point! It would suggest that nondeterministic algorithms somehow can't be executed by machines, when the whole point is that they can be. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 21:10, 6 July 2015 (UTC)